PreprintarXiv licencearXiv
A short proof of a range-relative FPTAS for polynomial integer optimization over bounded polyhedra
Abstract
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.
Related
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
- Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization
- A Bounded Degree SOS Plus SONC Hierarchy for Polynomial Optimization
- On the Krull dimensions of rings of integer-valued polynomials and polynomial rings
- Completing the Existence Problem for Integer Relative Heffter Arrays Hk(n;k)
BibTeX
@misc{hildebrand2026short,
title = {{A short proof of a range-relative FPTAS for polynomial integer optimization over bounded polyhedra}},
author = {Robert Hildebrand},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29573},
eprint = {2610.29573},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29573},
}
RIS
TY - UNPB
TI - A short proof of a range-relative FPTAS for polynomial integer optimization over bounded polyhedra
AU - Robert Hildebrand
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29573
UR - https://arxiv.org/abs/2610.29573
AB - 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.
ER -