  


Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane
Alberto Del Pia(alberto.delpiagmail.com) Abstract: We complete the complexity classification by degree of minimizing a polynomial in two variables over the integer points in a polyhedron. Previous work shows that in two variables, optimizing a quadratic polynomial over the integer points in a polyhedral region can be done in polynomial time, while optimizing a quartic polynomial in the same type of region is NPhard. We close the gap by showing that this problem can be solved in polynomial time for cubic polynomials. Furthermore, we show that the problem of minimizing a homogeneous polynomial in two variables of any fixed degree over the integer points in a bounded polyhedron is solvable in polynomial time. We show that this holds for polynomials that can be translated into homogeneous polynomials, even when the translation vector is unknown. We demonstrate that such problems in the unbounded case can have smallest optimal solutions of exponential size in the size of the input, thus requiring a compact representation of solutions for a general polynomial time algorithm for the unbounded case. Keywords: Integer Polynomial Minimization Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Download: [PDF] Entry Submitted: 08/20/2014 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  