pipette
ENEnglish

A short proof of a range-relative FPTAS for polynomial integer optimization over bounded polyhedra

Robert Hildebrand

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.