Metraipolis › archive › dc_3c0abebe693a

An ETH-Tight, Constructive FPT Algorithm for the Cone and Polytope Intersection Problem — arXiv:2609.31328

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.31328
License (as archived)
CC0-1.0
Archived
2026-10-08T03:35:17.799Z
SHA-256 of the archived text
10c6c907f0ba298ea4e6f636b986d17e1231fb486a00a7d249cc6751013491d9
Stable URL of this page
https://metraipolis.com/documento/dc_3c0abebe693a

How to cite

An ETH-Tight, Constructive FPT Algorithm for the Cone and Polytope Intersection Problem — arXiv:2609.31328 — arXiv (en), https://arxiv.org/abs/2609.31328 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3c0abebe693a (Metraipolis archive dc_3c0abebe693a, sha256 10c6c907f0ba298ea4e6f636b986d17e1231fb486a00a7d249cc6751013491d9)
BibTeX
@misc{dc3c0abebe693a,
  title = {An ETH-Tight, Constructive FPT Algorithm for the Cone and Polytope Intersection Problem — arXiv:2609.31328},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.31328},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3c0abebe693a; sha256 10c6c907f0ba298ea4e6f636b986d17e1231fb486a00a7d249cc6751013491d9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31328. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 Cone and Polytope Intersection problem: finding a vector $y \in \operatorname{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é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)}.$$ 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 $|\text{supp}(\lambda)| \le 2^{2d+1}$ in single-exponential FPT time.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.31328 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T03:12:28.092Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).