A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing

Felix Ohnesorge; Klaus Jansen; Lis Pirotton

arxiv: 2512.02691 · v3 · pith:BEBSJ7B3new · submitted 2025-12-02 · 💻 cs.CC · cs.DS

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing

Klaus Jansen , Felix Ohnesorge , Lis Pirotton This is my paper

Pith reviewed 2026-05-21 18:54 UTC · model grok-4.3

classification 💻 cs.CC cs.DS

keywords high-multiplicity bin packingexponential time hypothesislower boundsparameterized complexityinteger linear programming3-SAT reductiondoubly exponential time

0 comments

The pith

Unless the ETH fails, high-multiplicity Bin Packing has no algorithm running in time |I|^{2^{o(d)}}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a conditional lower bound showing that high-multiplicity Bin Packing with d distinct item types cannot be solved in time |I| raised to a sub-double-exponential function of d. This matches the runtime of the known algorithm by Goemans and Rothvoss up to the precise exponent, answering a question left open since 2014. The proof introduces a reduction from 3-SAT that packs the information of an n-variable instance into an integer linear program using only O(log n) variables and constraints. A sympathetic reader would conclude that the double-exponential dependence on the number of item types is necessary for any algorithm whose runtime is polynomial in the input size for fixed d.

Core claim

We show 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.

What carries the argument

A novel reduction from 3-SAT to an ILP formulation of high-multiplicity Bin Packing that encodes an n-variable instance using only O(log n) variables and constraints.

Load-bearing premise

The novel reduction from 3-SAT that efficiently encodes all information from a 3-SAT instance with n variables into an ILP with O(log(n)) variables and constraints is correct and runs in polynomial time.

What would settle it

An explicit algorithm that solves high-multiplicity Bin Packing instances with d item types in time |I|^{2^{o(d)}} for arbitrarily large d, or a direct refutation of the ETH.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper closes the Goemans-Rothvoss open question with an ETH lower bound for high-multiplicity bin packing via a compact 3-SAT to O(log n)-variable ILP reduction.

read the letter

The key takeaway is that unless ETH fails, high-multiplicity bin packing has no |I|^{2^{o(d)}} algorithm. The paper matches the known upper bound from Goemans and Rothvoss up to the constant in the exponent, which settles the main open problem they left in 2014 and 2020. The new element is a direct reduction from 3-SAT that encodes an n-variable formula into an ILP with only O(log n) variables and constraints; the coefficients and multiplicities then become the item sizes and counts in the bin-packing instance. If the encoding stays polynomial in n and preserves yes/no answers, the ETH hardness carries over cleanly without circularity. That construction is the main technical contribution and appears to be absent from earlier lower-bound work on this problem. The argument is self-contained and does not lean on the upper-bound algorithm itself. The reduction is presented as running in polynomial time with |I| polynomial in n while keeping d = O(log n), which is what makes the composed runtime contradict ETH. On the downside, the load-bearing step is verifying that the bit lengths of the O((log n)^2) numbers do not explode and that the mapping from clauses to coefficients is both correct and efficient. Any hidden exponential blow-up in constructing those integers would break the ETH implication, so the explicit construction and its correctness proof need close inspection. Minor gaps in the abstract description are expected, but the full write-up should make the encoding transparent. This work is aimed at researchers in parameterized complexity and fine-grained algorithms for packing problems. Readers who follow ETH-based lower bounds for XP problems will find it directly useful. It deserves a serious referee because it resolves a stated open question with a new encoding technique rather than incremental improvement. I would send it out for review.

Referee Report

2 major / 2 minor

Summary. The paper establishes a conditional lower bound for high-multiplicity Bin Packing parameterized by the number d of distinct item types. Under the Exponential Time Hypothesis, it claims there is no algorithm solving such instances in time |I|^{2^{o(d)}}, where |I| denotes the encoding length of the instance. The proof proceeds via a direct reduction from 3-SAT that, in polynomial time, produces a high-multiplicity Bin Packing instance whose encoding length is polynomial in the 3-SAT parameter n while using only d = O(log n) distinct item types; this is achieved by encoding an n-variable 3-SAT formula into an ILP with O(log n) variables and constraints whose coefficients and right-hand sides become the item sizes and multiplicities.

Significance. If the reduction is correct, the result resolves the open question posed by Goemans and Rothvoss (J.ACM'20) on whether the doubly exponential dependence on d in their SODA'14 algorithm is necessary. It supplies a direct ETH-based lower bound that does not reduce to or rely upon the existing upper-bound algorithm, confirming that the Goemans-Rothvoss runtime is essentially tight for XP algorithms parameterized by d. The compact O(log n)-variable encoding technique is a technical contribution that strengthens the lower-bound machinery.

major comments (2)

[Reduction construction] The reduction (described in the abstract and presumably detailed in the construction section): the claim that an n-variable 3-SAT instance can be encoded in polynomial time into an ILP with O(log n) variables, O(log n) constraints, and coefficients/right-hand sides of total bit length poly(n) is load-bearing for the entire lower bound. The manuscript must explicitly verify that the mapping from clauses to coefficient bits preserves satisfiability, that the resulting |I| remains polynomial in n, and that no super-polynomial blow-up occurs in the bit lengths; otherwise the composed runtime |I|^{2^{o(d)}} does not yield a 2^{o(n)} algorithm for 3-SAT and the ETH contradiction fails.
[Main theorem] Theorem stating the main lower bound: the runtime bound |I|^{2^{o(d)}} is derived directly from the reduction parameters; any gap in the polynomial-time claim or in the bit-length analysis would invalidate the o(d) exponent in the lower bound.

minor comments (2)

[Abstract] The abstract could include one sentence summarizing the key technical device (the O(log n)-variable ILP encoding) to help readers immediately grasp the novelty.
[Preliminaries] Notation for |I| (encoding length) versus the number of items should be introduced once and used consistently throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for acknowledging the significance of resolving the open question from Goemans and Rothvoss. We respond to each major comment below.

read point-by-point responses

Referee: [Reduction construction] The reduction (described in the abstract and presumably detailed in the construction section): the claim that an n-variable 3-SAT instance can be encoded in polynomial time into an ILP with O(log n) variables, O(log n) constraints, and coefficients/right-hand sides of total bit length poly(n) is load-bearing for the entire lower bound. The manuscript must explicitly verify that the mapping from clauses to coefficient bits preserves satisfiability, that the resulting |I| remains polynomial in n, and that no super-polynomial blow-up occurs in the bit lengths; otherwise the composed runtime |I|^{2^{o(d)}} does not yield a 2^{o(n)} algorithm for 3-SAT and the ETH contradiction fails.

Authors: The construction section provides a complete, explicit description of the reduction. Each clause of the 3-SAT instance is mapped to specific bits in the coefficients of the O(log n) ILP variables such that a satisfying assignment corresponds exactly to a feasible ILP solution (hence a feasible bin-packing solution) while an unsatisfiable formula yields an infeasible instance; the correctness of this mapping is established by a direct equivalence argument between the two problems. The section also contains a polynomial-time algorithm for producing the instance together with a bit-length analysis showing that all coefficients and right-hand sides have O(log n) bits and that the overall encoding length |I| is polynomial in n, with no super-polynomial blow-up. These bounds are used to prove that any |I|^{2^{o(d)}}-time algorithm for high-multiplicity bin packing would yield a 2^{o(n)}-time algorithm for 3-SAT. revision: no
Referee: [Main theorem] Theorem stating the main lower bound: the runtime bound |I|^{2^{o(d)}} is derived directly from the reduction parameters; any gap in the polynomial-time claim or in the bit-length analysis would invalidate the o(d) exponent in the lower bound.

Authors: Theorem 1.1 derives the stated lower bound directly from the parameters established in the construction: d = O(log n) and |I| polynomial in n. Substituting these values shows that 2^{o(d)} = n^{o(1)}, so an algorithm running in |I|^{2^{o(d)}} time would solve the reduced 3-SAT instance in 2^{o(n)} time, contradicting the ETH. The proof of the theorem includes the necessary polynomial-time and bit-length arguments to close any potential gaps. revision: no

Circularity Check

0 steps flagged

Direct ETH reduction from 3-SAT is self-contained with no circular steps

full rationale

The paper derives its lower bound via an explicit novel reduction from 3-SAT that encodes an n-variable instance into an ILP with O(log n) variables and constraints whose encoding length |I| remains polynomial in n. This construction is presented as independent of the cited Goemans-Rothvoss upper bound and rests on the external ETH assumption rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation. No equation or step in the provided derivation reduces to its own inputs by construction; the claimed polynomial-time encoding supplies new content that would yield a 2^{o(n)} 3-SAT algorithm if a |I|^{2^{o(d)}} solver existed.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the ETH and on the correctness of the newly introduced reduction; no numerical parameters are fitted and no new entities are postulated.

axioms (1)

domain assumption Exponential Time Hypothesis (ETH)
The lower bound holds only if ETH is true; the paper explicitly conditions the result on ETH not failing.

pith-pipeline@v0.9.0 · 5766 in / 1253 out tokens · 54045 ms · 2026-05-21T18:54:42.803761+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 1 internal anchor

[1]

Forall- exist statements in pseudopolynomial time

1 Eleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss, and Robert Weismantel. Forall- exist statements in pseudopolynomial time. InSODA, pages 2225–2233. SIAM, 2025.doi: 10.1137/1.9781611978322.73. 2 Piotr Berman, Marek Karpinski, and Alexander D. Scott. Computational complexity of some restricted instances of 3-sat.Discret. Appl. Math., 155(5):649–653,

work page doi:10.1137/1.9781611978322.73 2025
[2]

3 William J

URL:https: //doi.org/10.1016/j.dam.2006.07.009,doi:10.1016/J.DAM.2006.07.009. 3 William J. Cook, Mark Hartmann, Ravi Kannan, and Colin McDiarmid. On integer points in polyhedra.Comb., 12(1):27–37, 1992.doi:10.1007/BF01191202. 4 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurab...

work page doi:10.1016/j.dam.2006.07.009 2006
[3]

6 Josep Díaz, Olli Pottonen, Maria J

doi:10.1007/978-3-319-21275-3. 5 Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal.SIAM J. Comput., 45(1):67–83, 2016.doi:10.1137/130947076. 6 Friedrich Eisenbrand and Gennady Shmonin. Carathéodory bounds for integer cones.Oper. Res. Lett., 34(5):564–568,

work page doi:10.1007/978-3-319-21275-3 2016
[4]

7 Fedor V

URL:https://doi.org/10.1016/j.orl.2005.09.008, doi: 10.1016/J.ORL.2005.09.008. 7 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: hamiltonian cycle and the odd case of graph coloring.ACM Trans. Algorithms, 15(1):9:1–9:27, 2019.doi:10.1145/3280824. 8 Robert Fortet. Applications de l’algebre de boole e...

work page doi:10.1016/j.orl.2005.09.008 2005
[5]

URL:https://doi.org/10.1287/opre.9. 6.849. 10 Fred W. Glover and Eugene Woolsey. Technical note - converting the 0-1 polynomial programming problem to a 0-1 linear program.Oper. Res., 22(1):180–182,

work page doi:10.1287/opre.9
[6]

Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program

URL: https://doi.org/10.1287/opre.22.1.180,doi:10.1287/OPRE.22.1.180. 11 Michel X. Goemans and Thomas Rothvoss. Polynomiality for bin packing with a constant number of item types.J. ACM, 67(6):38:1–38:21, 2020.doi:10.1145/3421750. 12 Mark E. Hartmann. Cutting planes and the complexity of the integer hull . Technical report, Cornell University, 09

work page doi:10.1287/opre.22.1.180 2020
[7]

Integer multiplication in time 𝑂 (𝑛 log 𝑛),

URL:https://hdl.handle.net/1813/8702. 13 David Harvey and Joris van der Hoeven. Integer multiplication in time o(nlog n).Annals of Mathematics, 193(2):563–617, 2021.doi:10.4007/annals.2021.193.2.4. 14 Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, and Asaf Levin. Tight lower bounds for block-structured integer programs.Mat...

work page doi:10.4007/annals.2021.193.2.4 2021
[8]

URL:https://doi.org/10.1007/s10107-025-02296-z. K. Jansen, F. Ohnesorge and L. Pirotton 15 15 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In39th Annual Symposium on Foundations of Computer Science, FOCS, pages 653–663. IEEE Computer Society, 1998.doi:10.1109/SFCS.1998.743516. 16 Russell Imp...

work page doi:10.1007/s10107-025-02296-z 1998
[9]

Which problems have strongly exponential complexity? J

URL: https://doi.org/ 10.1006/jcss.2001.1774,doi:10.1006/JCSS.2001.1774. 17 Klaus Jansen and Kim-Manuel Klein. About the structure of the integer cone and its application to bin packing.Math. Oper. Res., 45(4):1498–1511,

work page doi:10.1006/jcss.2001.1774 2001
[10]

18 Klaus Jansen, Kim-Manuel Klein, and Alexandra Lassota

URL:https://doi.org/10.1287/ moor.2019.1040,doi:10.1287/MOOR.2019.1040. 18 Klaus Jansen, Kim-Manuel Klein, and Alexandra Lassota. The double exponential runtime is tight for 2-stage stochastic ilps.Math. Program., 197(2):1145–1172,

work page doi:10.1287/moor.2019.1040 2019
[11]

19 KlausJansen, StefanKratsch, DánielMarx, andIldikóSchlotter

URL:https: //doi.org/10.1007/s10107-022-01837-0,doi:10.1007/S10107-022-01837-0. 19 KlausJansen, StefanKratsch, DánielMarx, andIldikóSchlotter. Binpackingwithfixednumber of bins revisited.J. Comput. Syst. Sci., 79(1):39–49, 2013.doi:10.1016/J.JCSS.2012.04.004. 20 Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for schedulin...

work page doi:10.1007/s10107-022-01837-0 2013
[12]

22 Klaus Jansen, Lis Pirotton, and Malte Tutas

doi:10.1016/0304-3975(94)00230-G. 22 Klaus Jansen, Lis Pirotton, and Malte Tutas. The support of bin packing is exponential. In European Symposium on Algorithms, ESA, volume 351 ofLIPIcs, pages 48:1–48:16. Schloss Dag- stuhl - Leibniz-Zentrum für Informatik, 2025.arXiv:https://macau.uni-kiel.de/receive/ macau_mods_00006792?lang=en. 23 Klaus Jansen and Rob...

work page doi:10.1016/0304-3975(94)00230-g 2025
[13]

IVOA Recommendation: VOResource: an XML Encoding Schema for Resource Metadata Version 1.03

URL:https://doi.org/10.1287/moor.1110.0515,doi:10.1287/MOOR.1110.0515. 24 Volker Kaibel and Stefan Weltge. Lower bounds on the sizes of integer programs without additional variables.Math. Program., 154(1-2):407–425,

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1287/moor.1110.0515
[14]

1007/s10107-014-0855-0,doi:10.1007/S10107-014-0855-0

URL:https://doi.org/10. 1007/s10107-014-0855-0,doi:10.1007/S10107-014-0855-0. 25 Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. Parameterized complexity of configuration integer programs.Oper. Res. Lett., 49(6):908–913,

work page doi:10.1007/s10107-014-0855-0
[15]

26 Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn

URL: https://doi.org/10.1016/j.orl.2021.11.005,doi:10.1016/J.ORL.2021.11.005. 26 Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. High- multiplicity n-fold IP via configuration LP.Math. Program., 200(1):199–227,

work page doi:10.1016/j.orl.2021.11.005 2021
[16]

27 DusanKnop, MichalPilipczuk, andMarcinWrochna

URL: https://doi.org/10.1007/s10107-022-01882-9,doi:10.1007/S10107-022-01882-9. 27 DusanKnop, MichalPilipczuk, andMarcinWrochna. Tight complexitylowerbounds forinteger linear programming with few constraints.ACM Trans. Comput. Theory, 12(3):19:1–19:19, 2020.doi:10.1145/3397484. 28 Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, and M...

work page doi:10.1007/s10107-022-01882-9 2020
[17]

29 Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Wegrzycki

doi: 10.1137/1.9781611977936.25. 29 Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Wegrzycki. Coverability in VASS revisited: Improving rackoff’s bounds to obtain condi- tional optimality.J. ACM, 72(5):33:1–33:27, 2025.doi:10.1145/3762178. 30 Kenneth L. Manders and Leonard M. Adleman. Np-complete decision problems for qua...

work page doi:10.1137/1.9781611977936.25 2025
[18]

doi:10.1145/800113. 803627. 31 Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choos- ability problems parameterized by treewidth. In43rd International Colloquium on Automata, 16 A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing Languages, and Programming, ICALP, volume 55 ofLIPIcs, pages 28:1–28:1...

work page doi:10.1145/800113 2016
[19]

doi: 10.1007/BF01580665. 33 S. Thomas McCormick, Scott R. Smallwood, and Frits C. R. Spieksma. A polynomial algorithm for multiprocessor scheduling with two job lengths.Math. Oper. Res., 26(1):31–49,

work page doi:10.1007/bf01580665
[20]

34 Matthias Mnich and René van Bevern

URL: https://doi.org/10.1287/moor.26.1.31.10590,doi:10.1287/MOOR.26.1.31.10590. 34 Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems.Comput. Oper. Res., 100:254–261,

work page doi:10.1287/moor.26.1.31.10590
[21]

Automatic reconstruction of parametric building models from indoor point clouds

URL:https://doi.org/10.1016/j. cor.2018.07.020,doi:10.1016/J.COR.2018.07.020. 35 Alexander Schrijver.Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley,

work page doi:10.1016/j 2018
[22]

36 Craig A. Tovey. A simplified np-complete satisfiability problem.Discret. Appl. Math., 8(1):85– 89, 1984.doi:10.1016/0166-218X(84)90081-7. A Omitted Proofs A.1 Proof of Lemma 5 ▶ Lemma 5( /cu◎, Well-Structured 3-SAT; Extension of [ 36]).Given any instance of 3-SAT with n variables andm =O(n)clauses, there exists an equivalent instance withn′=O(n) variab...

work page doi:10.1016/0166-218x(84)90081-7 1984

[1] [1]

Forall- exist statements in pseudopolynomial time

1 Eleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss, and Robert Weismantel. Forall- exist statements in pseudopolynomial time. InSODA, pages 2225–2233. SIAM, 2025.doi: 10.1137/1.9781611978322.73. 2 Piotr Berman, Marek Karpinski, and Alexander D. Scott. Computational complexity of some restricted instances of 3-sat.Discret. Appl. Math., 155(5):649–653,

work page doi:10.1137/1.9781611978322.73 2025

[2] [2]

3 William J

URL:https: //doi.org/10.1016/j.dam.2006.07.009,doi:10.1016/J.DAM.2006.07.009. 3 William J. Cook, Mark Hartmann, Ravi Kannan, and Colin McDiarmid. On integer points in polyhedra.Comb., 12(1):27–37, 1992.doi:10.1007/BF01191202. 4 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurab...

work page doi:10.1016/j.dam.2006.07.009 2006

[3] [3]

6 Josep Díaz, Olli Pottonen, Maria J

doi:10.1007/978-3-319-21275-3. 5 Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal.SIAM J. Comput., 45(1):67–83, 2016.doi:10.1137/130947076. 6 Friedrich Eisenbrand and Gennady Shmonin. Carathéodory bounds for integer cones.Oper. Res. Lett., 34(5):564–568,

work page doi:10.1007/978-3-319-21275-3 2016

[4] [4]

7 Fedor V

URL:https://doi.org/10.1016/j.orl.2005.09.008, doi: 10.1016/J.ORL.2005.09.008. 7 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: hamiltonian cycle and the odd case of graph coloring.ACM Trans. Algorithms, 15(1):9:1–9:27, 2019.doi:10.1145/3280824. 8 Robert Fortet. Applications de l’algebre de boole e...

work page doi:10.1016/j.orl.2005.09.008 2005

[5] [5]

URL:https://doi.org/10.1287/opre.9. 6.849. 10 Fred W. Glover and Eugene Woolsey. Technical note - converting the 0-1 polynomial programming problem to a 0-1 linear program.Oper. Res., 22(1):180–182,

work page doi:10.1287/opre.9

[6] [6]

Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program

URL: https://doi.org/10.1287/opre.22.1.180,doi:10.1287/OPRE.22.1.180. 11 Michel X. Goemans and Thomas Rothvoss. Polynomiality for bin packing with a constant number of item types.J. ACM, 67(6):38:1–38:21, 2020.doi:10.1145/3421750. 12 Mark E. Hartmann. Cutting planes and the complexity of the integer hull . Technical report, Cornell University, 09

work page doi:10.1287/opre.22.1.180 2020

[7] [7]

Integer multiplication in time 𝑂 (𝑛 log 𝑛),

URL:https://hdl.handle.net/1813/8702. 13 David Harvey and Joris van der Hoeven. Integer multiplication in time o(nlog n).Annals of Mathematics, 193(2):563–617, 2021.doi:10.4007/annals.2021.193.2.4. 14 Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, and Asaf Levin. Tight lower bounds for block-structured integer programs.Mat...

work page doi:10.4007/annals.2021.193.2.4 2021

[8] [8]

URL:https://doi.org/10.1007/s10107-025-02296-z. K. Jansen, F. Ohnesorge and L. Pirotton 15 15 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In39th Annual Symposium on Foundations of Computer Science, FOCS, pages 653–663. IEEE Computer Society, 1998.doi:10.1109/SFCS.1998.743516. 16 Russell Imp...

work page doi:10.1007/s10107-025-02296-z 1998

[9] [9]

Which problems have strongly exponential complexity? J

URL: https://doi.org/ 10.1006/jcss.2001.1774,doi:10.1006/JCSS.2001.1774. 17 Klaus Jansen and Kim-Manuel Klein. About the structure of the integer cone and its application to bin packing.Math. Oper. Res., 45(4):1498–1511,

work page doi:10.1006/jcss.2001.1774 2001

[10] [10]

18 Klaus Jansen, Kim-Manuel Klein, and Alexandra Lassota

URL:https://doi.org/10.1287/ moor.2019.1040,doi:10.1287/MOOR.2019.1040. 18 Klaus Jansen, Kim-Manuel Klein, and Alexandra Lassota. The double exponential runtime is tight for 2-stage stochastic ilps.Math. Program., 197(2):1145–1172,

work page doi:10.1287/moor.2019.1040 2019

[11] [11]

19 KlausJansen, StefanKratsch, DánielMarx, andIldikóSchlotter

URL:https: //doi.org/10.1007/s10107-022-01837-0,doi:10.1007/S10107-022-01837-0. 19 KlausJansen, StefanKratsch, DánielMarx, andIldikóSchlotter. Binpackingwithfixednumber of bins revisited.J. Comput. Syst. Sci., 79(1):39–49, 2013.doi:10.1016/J.JCSS.2012.04.004. 20 Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for schedulin...

work page doi:10.1007/s10107-022-01837-0 2013

[12] [12]

22 Klaus Jansen, Lis Pirotton, and Malte Tutas

doi:10.1016/0304-3975(94)00230-G. 22 Klaus Jansen, Lis Pirotton, and Malte Tutas. The support of bin packing is exponential. In European Symposium on Algorithms, ESA, volume 351 ofLIPIcs, pages 48:1–48:16. Schloss Dag- stuhl - Leibniz-Zentrum für Informatik, 2025.arXiv:https://macau.uni-kiel.de/receive/ macau_mods_00006792?lang=en. 23 Klaus Jansen and Rob...

work page doi:10.1016/0304-3975(94)00230-g 2025

[13] [13]

IVOA Recommendation: VOResource: an XML Encoding Schema for Resource Metadata Version 1.03

URL:https://doi.org/10.1287/moor.1110.0515,doi:10.1287/MOOR.1110.0515. 24 Volker Kaibel and Stefan Weltge. Lower bounds on the sizes of integer programs without additional variables.Math. Program., 154(1-2):407–425,

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1287/moor.1110.0515

[14] [14]

1007/s10107-014-0855-0,doi:10.1007/S10107-014-0855-0

URL:https://doi.org/10. 1007/s10107-014-0855-0,doi:10.1007/S10107-014-0855-0. 25 Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. Parameterized complexity of configuration integer programs.Oper. Res. Lett., 49(6):908–913,

work page doi:10.1007/s10107-014-0855-0

[15] [15]

26 Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn

URL: https://doi.org/10.1016/j.orl.2021.11.005,doi:10.1016/J.ORL.2021.11.005. 26 Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. High- multiplicity n-fold IP via configuration LP.Math. Program., 200(1):199–227,

work page doi:10.1016/j.orl.2021.11.005 2021

[16] [16]

27 DusanKnop, MichalPilipczuk, andMarcinWrochna

URL: https://doi.org/10.1007/s10107-022-01882-9,doi:10.1007/S10107-022-01882-9. 27 DusanKnop, MichalPilipczuk, andMarcinWrochna. Tight complexitylowerbounds forinteger linear programming with few constraints.ACM Trans. Comput. Theory, 12(3):19:1–19:19, 2020.doi:10.1145/3397484. 28 Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, and M...

work page doi:10.1007/s10107-022-01882-9 2020

[17] [17]

29 Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Wegrzycki

doi: 10.1137/1.9781611977936.25. 29 Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Wegrzycki. Coverability in VASS revisited: Improving rackoff’s bounds to obtain condi- tional optimality.J. ACM, 72(5):33:1–33:27, 2025.doi:10.1145/3762178. 30 Kenneth L. Manders and Leonard M. Adleman. Np-complete decision problems for qua...

work page doi:10.1137/1.9781611977936.25 2025

[18] [18]

doi:10.1145/800113. 803627. 31 Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choos- ability problems parameterized by treewidth. In43rd International Colloquium on Automata, 16 A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing Languages, and Programming, ICALP, volume 55 ofLIPIcs, pages 28:1–28:1...

work page doi:10.1145/800113 2016

[19] [19]

doi: 10.1007/BF01580665. 33 S. Thomas McCormick, Scott R. Smallwood, and Frits C. R. Spieksma. A polynomial algorithm for multiprocessor scheduling with two job lengths.Math. Oper. Res., 26(1):31–49,

work page doi:10.1007/bf01580665

[20] [20]

34 Matthias Mnich and René van Bevern

URL: https://doi.org/10.1287/moor.26.1.31.10590,doi:10.1287/MOOR.26.1.31.10590. 34 Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems.Comput. Oper. Res., 100:254–261,

work page doi:10.1287/moor.26.1.31.10590

[21] [21]

Automatic reconstruction of parametric building models from indoor point clouds

URL:https://doi.org/10.1016/j. cor.2018.07.020,doi:10.1016/J.COR.2018.07.020. 35 Alexander Schrijver.Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley,

work page doi:10.1016/j 2018

[22] [22]

36 Craig A. Tovey. A simplified np-complete satisfiability problem.Discret. Appl. Math., 8(1):85– 89, 1984.doi:10.1016/0166-218X(84)90081-7. A Omitted Proofs A.1 Proof of Lemma 5 ▶ Lemma 5( /cu◎, Well-Structured 3-SAT; Extension of [ 36]).Given any instance of 3-SAT with n variables andm =O(n)clauses, there exists an equivalent instance withn′=O(n) variab...

work page doi:10.1016/0166-218x(84)90081-7 1984