An ETH-Tight, Constructive FPT Algorithm for the Cone and Polytope Intersection Problem

In a landmark paper, Goemans and Rothvoss (2020) established an XP algorithm running in time $enc(P{)}^{2^{O(d)}}\cdot enc(Q{)}^{O(1)}$ for the Cone and Polytope Intersection problem: finding a vector $y\in int.cone(P\cap {\mathbb{Z}}^d)\cap Q$ together with a sparse certificate $\lambda \in {\mathbb{Z}}_{\ge 0}^{P\cap {\mathbb{Z}}^d}$ supported on at most $2^{2d+1}$ generators, where $P\subseteq {\mathbb{R}}^d$ is a bounded rational polyhedron and $Q\subseteq {\mathbb{R}}^d$ is an arbitrary rational polyhedron. For high-multiplicity bin packing, this gives a running time of ${|I|}^{2^{O(d)}}$, where $|I|$ denotes the encoding length of the input. Recently, Koana and Kumabe (2026) proved that the decision variant of this problem is fixed-parameter tractable (FPT) parameterized by the number of item types $d$ with running time $2^{d^{O(d)}}\cdot {|I|}^{O(1)}=2^{2^{O(d\log d)}}\cdot {|I|}^{O(1)}$. In this work, we generalize the framework of Koana and Kumabe from standard bin packing to the full Cone and Polytope Intersection Problem of Goemans and Rothvoss, directly encompassing high-multiplicity bin packing, point-in-cone, and scheduling. Secondly, by combining Carath\'eodory-type integer cone bounds (Eisenbrand and Shmonin, 2006) with active support enumeration, we reduce the running time to: $2^{2^{O(d)}}\cdot (enc(P)+enc(Q){)}^{O(1)}$. Under the Exponential Time Hypothesis (ETH), the double-exponential lower bound of Kowalik, Lassota, Majewski, Pilipczuk, and Soko{\l}owski (2024) for point-in-cone and Jansen, Ohnesorge, and Pirotton (2026) for high-multiplicity bin packing implies that this parameter dependence is asymptotically optimal. Finally, we provide an explicit decompression algorithm that extracts a solution with sparse support $|supp(\lambda )|\le 2^{2d+1}$ in single-exponential FPT time.