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 $\text{enc}(P{)}^{2^{O(d)}}\cdot \text{enc}(Q{)}^{O(1)}$ for the \emph{Cone and Polytope Intersection} problem: finding a vector $y\in \text{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 ${\mathrm{\mid }I\mathrm{\mid }}^{2^{O(d)}}$, where $\mathrm{\mid }I\mathrm{\mid }$ 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 {\mathrm{\mid }I\mathrm{\mid }}^{O(1)}=2^{2^{O(d\log d)}}\cdot {\mathrm{\mid }I\mathrm{\mid }}^{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éodory-type integer cone bounds (Eisenbrand and Shmonin, 2006) with active support enumeration, we reduce the running time to: $$2^{2^{O(d)}}\cdot (\text{enc}(P)+\text{enc}(Q){)}^{O(1)}\text{.}$$ Under the Exponential Time Hypothesis (ETH), the double-exponential lower bound of Kowalik, Lassota, Majewski, Pilipczuk, and Sokoł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 $\mathrm{\mid }\text{supp}(\lambda )\mathrm{\mid }\le 2^{2d+1}$ in single-exponential FPT time.