Optimization Online


Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane

Alberto Del Pia(alberto.delpia***at***gmail.com)
Robert Hildebrand(robert.hildebrand***at***ifor.math.ethz.ch)
Robert Weismantel(robert.weismantel***at***ifor.math.ethz.ch)
Kevin Zemmer(kevin.zemmer***at***ifor.math.ethz.ch)

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 NP-hard. 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 )


Download: [PDF]

Entry Submitted: 08/20/2014
Entry Accepted: 08/20/2014
Entry Last Modified: 08/20/2014

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 Optimization Society