Preprint
Sep 2026
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 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 \i...
Klaus Jansen, Felix Ohnesorge
· 0 citations