Establishes a tight double-exponential lower bound for high-multiplicity bin packing parameterized by number of distinct item types d, showing no |I|^{2^{o(d)}} algorithm exists unless ETH fails, via a novel 3-SAT reduction to an ILP with O(log n) variables.
Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
verdicts
UNVERDICTED 2representative citing papers
Extends a 2023 result on relaxation dominance in multilinear optimization to broader linearizations, supplies a simpler proof, and proves that the intersection with the extended flower relaxation is equivalent in strength.
citing papers explorer
-
A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
Establishes a tight double-exponential lower bound for high-multiplicity bin packing parameterized by number of distinct item types d, showing no |I|^{2^{o(d)}} algorithm exists unless ETH fails, via a novel 3-SAT reduction to an ILP with O(log n) variables.
-
Relaxation strength for multilinear optimization: McCormick strikes back
Extends a 2023 result on relaxation dominance in multilinear optimization to broader linearizations, supplies a simpler proof, and proves that the intersection with the extended flower relaxation is equivalent in strength.