TL;DR
This paper proves that deciding if a point lies within the integer cone of a bounded polytope is "double-exponentially hard" under the Exponential-Time Hypothesis (ETH). This means that any algorithm solving this problem must have a running time that grows at least doubly exponentially with the dimension of the space, even if the polytope and point are small. This result establishes a fundamental lower bound for a problem with applications in areas like bin packing.
What Problem Does This Paper Address?
The paper tackles the computational complexity of the "Point in Cone" problem. Specifically, given a bounded polytope $P$ in $d$-dimensional space and an integer point $q$, we want to determine if $q$ can be expressed as a non-negative integer linear combination of integer points within $P$. This problem is a simplification of the more general "Cone and Polytope Intersection" problem, which has direct applications in combinatorial optimization, such as the high-multiplicity bin packing problem.
While a previous algorithm by Goemans and Rothvoss provided a solution with a running time that was exponential in the dimension $d$ (specifically, $enc(P)^{O(d)}$), it was an open question whether this dependence on $d$ could be improved to something more manageable, like fixed-parameter tractability (i.e., $f(d) \cdot poly(enc(P), enc(q))$ for some function $f$). This paper addresses this by providing a conditional lower bound, showing that such an improvement is unlikely unless the Exponential-Time Hypothesis (ETH) is false. The ETH is a widely believed conjecture in theoretical computer science that implies certain problems, like 3-SAT, cannot be solved significantly faster than their brute-force exponential time complexity.
Methods
The core of the paper's contribution lies in a sophisticated reduction from a related problem called "Subset Sum with Multiplicities" to the "Point in Cone" problem. Here's a breakdown of the approach:
- Subset Sum with Multiplicities: This problem asks if a target integer $t$ can be formed by a non-negative integer linear combination of a given set of positive integers $\{a_1, \dots, a_n\}$. The paper first establishes a lower bound for this problem, showing it's "exponentially hard" (i.e., requires $2^{O(n)}$ time) under the ETH. This is done by reducing from the standard Subset Sum problem.
- Reduction to Point in Cone: The main technical contribution is a construction that transforms an instance of "Subset Sum with Multiplicities" into an instance of "Point in Cone."
- They define a $d$-dimensional space where $d$ is related to the logarithm of the number of items ($n$).
- They construct a set of $2^d$ points, which are then used to define a bounded polytope $P$. The coordinates of these points are carefully crafted using binary representations and the input integers $a_i$.
- A target point $q$ is also constructed based on the target sum $t$.
- The key insight is that a solution to the "Subset Sum with Multiplicities" instance exists if and only if the target point $q$ lies within the integer cone of the constructed polytope $P$.
- Encoding Size Analysis: A crucial part of the reduction is ensuring that the encoding size of the constructed polytope $P$ and point $q$ is not excessively large. They show that $enc(P, q)$ is polynomially related to the input size of the "Subset Sum with Multiplicities" instance (specifically, $O(n \log n \log t)$).
- Lower Bound Derivation: By combining the exponential lower bound for "Subset Sum with Multiplicities" with the polynomial-time reduction to "Point in Cone," they derive the double-exponential lower bound for "Point in Cone." If an algorithm for "Point in Cone" existed with a running time of $enc(P, q)^{O(d)}$, it would imply a faster-than-expected algorithm for "Subset Sum with Multiplicities," contradicting the ETH.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity and reductions, not empirical evaluation on specific datasets.
Key Insights and Ideas
- The Necessity of Double-Exponential Dependence: The most significant insight is that the dimension $d$ in problems involving integer cones of polytopes is inherently difficult. The paper demonstrates that any algorithm must contend with a doubly exponential blow-up in running time with respect to $d$, assuming the ETH. This is a strong statement about the fundamental limits of computation for this class of problems.
- A Novel Reduction Gadget: The construction of the polytope $P$ and the target point $q$ from the "Subset Sum with Multiplicities" instance is a novel technical contribution. It cleverly uses binary representations and the structure of the problem to create a geometric instance that mirrors the algebraic nature of subset sum.
- Bridging Combinatorial Optimization and Complexity Theory: The paper connects a practical problem in combinatorial optimization (bin packing) to deep theoretical questions in complexity theory (ETH). It shows how understanding the hardness of fundamental geometric problems can inform our understanding of the complexity of applied problems.
- Tightness of Existing Algorithms: The result implies that the $2^{O(d)}$ factor in the running time of Goemans and Rothvoss's algorithm is likely unavoidable, at least in terms of its dependence on $d$.
Key Results
- Conditional Double-Exponential Lower Bound: Unless the ETH fails, there is no algorithm that solves the "Point in Cone" problem (given a bounded polytope $P \subseteq \mathbb{R}^d$ and an integer point $q \in \mathbb{Z}^d$) in time $enc(P, q)^{O(d)}$. This means the running time must be at least $2^{\Omega(d)}$ in the exponent of the polynomial dependence on the encoding size.
- Tightness for Subset Sum with Multiplicities: The paper also proves that "Subset Sum with Multiplicities" is $2^{O(n)}$ hard under the ETH, where $n$ is the number of integers in the input set.
Limitations and Future Work
- Conditional Lower Bound: The result is conditional on the ETH. While the ETH is widely believed, it remains a conjecture.
- Focus on Dimension: The lower bound is specifically on the dependence on the dimension $d$. The dependence on the encoding size of the polytope and point ($enc(P, q)$) is still polynomial.
- Future Work: The paper's findings suggest that exploring algorithms with a doubly exponential dependence on $d$ might be necessary for optimal worst-case performance. Further research could investigate whether there are specific subclasses of polytopes or points for which faster algorithms exist, or explore alternative parameterizations of the problem. The authors also mention that tight doubly-exponential lower bounds are rare, suggesting this work contributes to a growing body of literature on the limits of efficient computation for certain problems.
Summary updated