Tight ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing

Prelegent(ci)

Anita Dürr

Afiliacja

ETH Zurich

Język referatu

angielski

Termin

8 maja 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

Bin Packing with k bins is a fundamental optimisation problem in which we are given a set of n integers and a capacity T and the goal is to partition the set into k subsets, each of total sum at most T. Bin Packing is NP-hard already for k = 2 and a textbook dynamic programming algorithm solves it in pseudopolynomial time O(nT^{k−1}). Jansen, Kratsch, Marx, and Schlotter [JCSS’13] proved that this time cannot be improved to (nT)^o(k/ log k) assuming the Exponential Time Hypothesis (ETH). Their result has become an important building block, explaining the hardness of many problems in parameterised complexity. Note that their result is one log-factor short of being tight. In this talk, I'll show a tight ETH-based lower bound for Bin Packing, ruling out time 2^o(n)T^o(k). This answers an open problem of Jansen et al. and yields improved lower bounds for many applications in parameterised complexity.

This is based on the following paper to appear at STOC26 https://arxiv.org/abs/2603.12999

---