  


A Faster Algorithm for Quasiconvex Integer Polynomial Optimization
Robert Hildebrand(rhildebrandmath.ucdavis.edu) Abstract: We present a faster exponentialtime algorithm for integer optimization over quasiconvex polynomials. We study the minimization of a quasiconvex polynomial subject to s quasiconvex 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 exponentialtime complexity of a Lenstratype algorithm. For the bounded case, our algorithm attains a timecomplexity 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: Quasiconvex integer optimization, Lenstra's algorithm Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Download: [PDF] Entry Submitted: 06/23/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  