Noticias en español
Adaptive bin packing with overflow.
Abstract: Motivated by the allocation of virtual machines into servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but upon arrival an item’s actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the decision maker observes the item’s actual size, and overflowing the bin is a possibility. An overflow incurs a large...
Read MoreCity logistics and smart delivery.
Abstract: he current and expected growing number of people living and working in cities and the limited space available inside city centres implies a greater exchange of inbound and outbound freight flows between city centres and their surrounding regions. Urban freight transports provide economic benefits to society but are also responsible for negative externalities such as congestion, air and water pollution, climate change, accidents and noise. Access restrictions are one of the most applied measures to control urban traffics in the city’s specific areas. A growing use of urban...
Read MoreWell-quasi-ordering digraphs by the strong immersion relation.
Abstract: A well-quasi-ordering is a reflexive and transitive binary relation such that every infinite sequence has a non-trivial increasing subsequence. The study of well-quasi-ordering was stimulated by two conjectures of Vazsonyi in 1940s: trees and subcubic graphs are well-quasi-ordered by the topological minor relation. It is known that the topological minor relation does not well-quasi-order all graphs. Nash-Williams in 1960s introduced the notion of strong immersion and conjectured that the strong immersion relation well-quasi-orders all graphs, which is a common generalization of...
Read MoreCounting integer partitions with the method of maximum entropy.
Abstract: The problem of asymptotically counting integer partitions has a long and storied history, beginning with the pioneering work of Hardy and Ramanujan in 1918. In the work presented here, we give a probabilistic perspective on this problem, and use this approach to prove an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer...
Read MoreMatroids, polymatroids and submodular functions: algebra or optimization?
Abstract: Matroids, polymatroids and submodular functions are beautiful objects that have appeared in many areas of mathematics including algebra, geometry, topology and optimization. Consequently, they have been studied from multiple points of view. This oftentimes has the consequence that the same results are proven from different points of view and by very different communities. A notable example being their study in optimization and algebraic combinatorics. The goal of this talk is to tell this story, show how a small mixture of ideas from different communities lead to powerful algebraic...
Read MoreAn optimal algorithm for strict circular seriation.
Abstract: Seriation is an exploratory combinatorial data analysis technique to reorder objects into a sequence along a one-dimensional continuum when the only available information among the objects is their pairwise similarity (or dissimilarity). Linear seriation aims at inferring an ordering (permutation) consistent with an underlying linear order of the data. In many cases however, the data objects may be arranged around a closed continuum yielding a rather circular underlying order. In a matrix representation, this can be visualized as a symmetric matrix of pairwise dissimilarities...
Read More