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

Speaker(s)

Anita Dürr

Affiliation

ETH Zurich

Language of the talk

English

Date

May 8, 2026, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

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

---