Ariel Kulik - Constrained Resource Allocation via Iterative Randomized Rounding

Constrained resource allocation problems can often be modeled as variants of the classic Bin Packing and Knapsack problems. The study of these problems has had a great impact on the development of algorithmic tools, ranging from simple dynamic programming to involved linear programs and rounding techniques. I will present a new and simple algorithmic approach for obtaining efficient approximations for such problems, based on iterative randomized rounding of Configuration LPs. This simple approach yields the state-of-the-art asymptotic approximation ratio for Vector Bin Packing and matches the best-known ratios for other variants of the Bin Packing problem. The technique can be used also to improve the existing results for Multiple Knapsack variants. While the algorithmic approach is simple and intuitive, its analysis requires sophisticated use of probabilistic tools and deep structural insights about the studied problems.