Noticias en español
A (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 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 More