Optimization Online


A Faster Algorithm for Quasi-convex Integer Polynomial Optimization

Robert Hildebrand(rhildebrand***at***math.ucdavis.edu)
Matthias Koeppe(mkoeppe***at***math.ucdavis.edu)

Abstract: We present a faster exponential-time algorithm for integer optimization over quasi-convex polynomials. We study the minimization of a quasi-convex polynomial subject to s quasi-convex polynomial constraints and integrality constraints for all variables. The new algorithm is an improvement upon the best known algorithm due to Heinz (Journal of Complexity, 2005). A lower time complexity is reached through applying a stronger ellipsoid rounding method and applying a recent advancement in the shortest vector problem to give a smaller exponential-time complexity of a Lenstra-type algorithm. For the bounded case, our algorithm attains a time-complexity of s (r l M d)^{O(1)} 2^{2n\log_2(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, s l^{O(1)} d^{O(n)} 2^{2n\log_2(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.

Keywords: Quasi-convex integer optimization, Lenstra's algorithm

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 06/23/2010
Entry Accepted: 06/24/2010
Entry Last Modified: 06/23/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society