Noticias en español
Stable matching games.
Abstract: Gale and Shapley (1962) introduced a matching problem between two sets of agents M and W, who need to be paired by taking into account that each agent on one side of the market has an exogenous preference order over the agents of the other side. They defined a matching as stable if no unmatched pair can both improve their payoffs by breaking their couples and forming a new one. They proved the existence of a stable matching using a deferred-acceptance algorithm. Shapley and Shubik (1971) extended the model by allowing monetary transfers. Our article offers a further extension by...
Read MoreA (2 + epsilon)-approximation algorithm for preemptive weighted flow time on a single machine.
Abstract: In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC’21) managed to improve this large unspecified constant to 2 + epsilon. I will give a very graphic presentation of the algorithmic techniques behind this.
Read MoreImproved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More.
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+eps<1.89 and there is a (3/2+eps)-approximation algorithm if we are allowed to rotate items by 90 degrees. In this talk, I will present a (4/3+eps)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers...
Read MoreScheduling in the Random-Oder Model.
Abstract: We study Online Makespan Minimization, one of the most basic scheduling problems, in the random-order model. Here jobs of a given input arrive in a uniformly chosen random order as opposed to the classical adversarial model, which considers worst-case orders. The random-order model originates from the Secretary Problem and has received quite some research interest over the last years. For scheduling, the random-order model provides beyond worst-case guarantees while still not being overly pessimistic. Furthermore, it leads to a stronger performance measure, which considers...
Read MoreAdaptive 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 More