A short proof of a range-relative FPTAS for polynomial integer optimization over bounded polyhedra
In the authors' words
We give a short proof of a fully polynomial-time range-relative approximation scheme for polynomial optimization over the integer points of a bounded rational polyhedron in fixed dimension. The proof combines the reflecting-set decomposition of Cook, Hartmann, Kannan, and McDiarmid with Markov's polynomial derivative inequality and uses one integer linear feasibility query per refined cell. The running time is polynomial in the input encoding size, numerical degree, and reciprocal accuracy.
Main resultLimitation the authors admit
Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.