Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Hildebrand, Robert; Weismantel, Robert; Zemmer, Kevin
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0738
• 发表日期: 2016
• 页码: 511-530
• 关键词: production sets; optimization; indivisibilities; complexity

摘要

We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in a real vector space of dimension two. Previous work shows that optimizing a quadratic polynomial over the integer points in a polyhedral region in a real vector space of dimension two can be done in polynomial time, whereas 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 of any fixed degree over the integer points in a bounded polyhedron in a real vector space of dimension two 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.