Reminder, this is happening today.
On Sun, Dec 17, 2023 at 4:12 PM Sagie Benaim sagie.benaim@mail.huji.ac.il wrote:
Dear all,
Next week, we have the pleasure of having Dr. Ariel Kulik give a talk in the colloquium.
The seminar will be held on Monday, December 25th at 14:00. Location: C220.
The title, abstract and bio appear below.
Looking forward to seeing you, Sagie and Liat
*Title*: Advances in Constrained Resource Allocation and Randomized Branching
*Abstract:* I will discuss two of my recent works which demonstrate how probabilistic tools can be used to attain simple yet powerful algorithms:
- 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.
- 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.
*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.