A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity 2O(nlogn)2O(nlogn)

We study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorithm due to Heinz [S. Heinz, Complexity of integer quasiconvex polynomial optimization, Journal of Complexity 21(4) (2005) 543–556]. This improvement is achieved by applying a new modern Lenstra-type algorithm, finding optimal ellipsoid roundings, and considering sparse encodings of polynomials. For the bounded case, our algorithm attains a time-complexity of s(rlMd)O(1)22nlog2(n)+O(n)s(rlMd)O(1)22nlog2(n)+O(n) when MM is a bound on the number of monomials in each polynomial and rr is the binary encoding length of a bound on the feasible region. In the general case, slO(1)dO(n)22nlog2(n)+O(n)slO(1)dO(n)22nlog2(n)+O(n). In each we assume d≥2d≥2 is a bound on the total degree of the polynomials and ll bounds the maximum binary encoding size of the input.