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

作者：Hildebrand Robert^*; Koeppe Matthias

来源：Discrete Optimization, 2013, 10(1): 69-84.

DOI：10.1016/j.disopt.2012.11.003

• Quasiconvex integer optimization
• Lenstra's algorithm
• SVP
• Ellipsoid rounding

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))2(2n) (log2(n)+O(n)) when M is a bound on the number of monomials in each polynomial and r is the binary encoding length of a bound on the feasible region. In the general case, sl(O(1))d(O(n))2(2n) (log2(n)+O(n)) In each we assume d >= 2 is a bound on the total degree of the polynomials and l bounds the maximum binary encoding size of the input.

• 出版日期2013-2