Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling

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 paper, we prove 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.

Since Bin Packing is an example of multi-machine scheduling, it is natural to next study other scheduling problems. We prove tight lower bounds based on the Strong Exponential Time Hypothesis (SETH) for several classic k-machine scheduling problems, including makespan minimisation with release dates (P k |r j |C max ), minimizing the number of tardy jobs (P k ||ΣU j ), and minimizing the weighted sum of completion times (P k ||Σw j C j ). For all these problems, we rule out time 2 o(n) T k-1-ε for any ε > 0 assuming SETH, where T is the total processing time; this matches classic n O(1) T k-1 -time algorithms from the 60s and 70s. Moreover, we rule out time 2 o(n) T k-ε for minimizing the total processing time of tardy jobs (P k ||Σp j U j ), which matches a classic O(nT k )-time algorithm and answers an open problem of Fischer and Wennmann [TheoretiCS'25].