2023/07/01 by Kowalik, Łukasz, Lassota, Alexandra, Majewski, Konrad +2 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2307.00406
Let d be a positive integer. For a finite set X ⊆ ℝd, we define its integer cone as the set IntCone(X) := \ ∑x ∈ X λx ⋅ x | λx ∈ ℤ≥ 0 \ ⊆ ℝd. Goemans and Rothvoss showed that, given two polytopes P, Q ⊆ ℝd with P being bounded, one can decide whether IntCone(P ∩ ℤd) intersects Q in time enc(P)^2O(d) ⋅ enc(Q)O(1) [J. ACM 2020], where enc(⋅) denotes the number of bits required to encode a polytope through a system of linear inequalities. This result is the cornerstone of their XP algorithm for BIN PACKING parameterized by the number of different item sizes. We complement their result by providing a conditional lower bound. In particular, we prove that, unless the ETH fails, there is no algorithm which, given a bounded polytope P ⊆ ℝd and a point q ∈ ℤd, decides whether q ∈ IntCone(P ∩ ℤd) in time enc(P, q)^2o(d). Note that this does not rule out the existence of a fixed-parameter tractable algorithm for the problem, but shows that dependence of the running time on the parameter d must be at least doubly-exponential.