2026-09-08T01:22:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26505 2026-09-05T19:46:07Z ddc:004 open_access

A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing Jansen, Klaus Ohnesorge, Felix Pirotton, Lis Bin Packing Lower Bound Computational Complexity ETH Consider a high-multiplicity Bin Packing instance I with d distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime (|I|²)^O(d) for this problem [SODA'14], where |I| denotes the encoding length of the instance I. Although Jansen and Klein [SODA'17] later developed an algorithm that improves upon this runtime in a special case, it has remained a major open problem by Goemans and Rothvoss [J.ACM'20] whether the doubly exponential dependency on d is necessary. We solve this open problem by showing that unless the Exponential Time Hypothesis (ETH) fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time (|I|²)^o(d). To prove this, we introduce a novel reduction from 3-SAT. The core of our construction is efficiently encoding all information from a 3-SAT instance with n variables into an ILP with O(log n) variables and constraints. This result confirms that the Goemans and Rothvoss algorithm is essentially best-possible for Bin Packing parameterized by the number d of item sizes in the context of XP time algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus Jansen and Felix Ohnesorge and Lis Pirotton 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.116 urn:nbn:de:0030-drops-265051 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.116 eng https://creativecommons.org/licenses/by/4.0/legalcode