קולקוויום מחלקתי 28.12.23

Advances in Constrained Resource Allocation and Randomized Branching

 
I will discuss two of my recent works which demonstrate how probabilistic tools can be
 used to attain simple yet powerful algorithms:

1. 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 sophisticated 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 art asymptotic
   approximation ratio for Vector Bin Packing, matches the state of art ratios
   for other variants of the Bin Packing problem, and is useful for Multiple Knapsack
   and its variants. While the approach is simple, its analysis requires profound
   understanding of probabilistic tools and deep structural insights about the
   studied problems.
 
2. Two prominent approaches for coping with NP-hard optimization problems are
   polynomial-time approximation and parameterized algorithms. In recent years,
   increasing attention has been given to the hybrid approach of parameterized-
   approximation algorithms,leading to both upper and lower bounds. I will show how an
   intuitive randomized branching technique can be used to obtain fast parameterized-
   approximation algorithms for some fundamental problems in graph theory. The running
   times of the resulting algorithms can be derived from recurrence relations in two
   variables, for which there was no known solution. A main technical contribution of
   this work is the analysis of such recurrences using tools from information theory.
   

Short Bio:

Ariel Kulik is currently a postdoctoral research associate at the Technion, hosted by
Roy Schwartz. Formerly, he was a postdoc at CISPA, hosted by Daniel Marx. Ariel
completed his PhD studies in Computer Science at the Technion, supervised by Hadas
Shachnai. His research focuses on the design and analysis of approximation algorithms
for constrained submodular optimization and resource allocation problems. He also
works on parameterized-approximation algorithms, with emphasis on tools for the
analysis of branching algorithms.