A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916022012870656 |
|---|---|
| author | Jansen, Klaus Ohnesorge, Felix Pirotton, Lis |
| author_facet | Jansen, Klaus Ohnesorge, Felix Pirotton, Lis |
| contents | Consider a high-multiplicity Bin Packing instance $I$ with $d$ distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime ${{|I|}^2}^{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 ETH fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time ${{|I|}^2}^{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02691 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing Jansen, Klaus Ohnesorge, Felix Pirotton, Lis Computational Complexity Data Structures and Algorithms Consider a high-multiplicity Bin Packing instance $I$ with $d$ distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime ${{|I|}^2}^{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 ETH fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time ${{|I|}^2}^{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. |
| title | A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.02691 |