Minimizing cubic and homogeneous polynomials over integers in the plane

DOI10.1287/MOOR.2015.0738zbMATH Open1338.90262DBLPjournals/mor/PiaHWZ16arXiv1408.4711OpenAlexW1740954773WikidataQ57568084 ScholiaQ57568084MaRDI QIDQ2806816FDOQ2806816

Authors: Alberto Del Pia, Robert Hildebrand, Robert Weismantel, Kevin Zemmer 

Publication date: 19 May 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: We complete the complexity classification by degree of minimizing a polynomial over the integer points in a polyhedron in $mathbb{R}^2$. Previous work shows that optimizing a quadratic polynomial over the integer points in a polyhedral region in $mathbb{R}^2$ 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 of any fixed degree over the integer points in a bounded polyhedron in $mathbb{R}^2$ 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.

Full work available at URL: https://arxiv.org/abs/1408.4711

Recommendations

• Integer quadratic programming in the plane
• Integer Polynomial Optimization in Fixed Dimension
• The efficient minimization of quadratic polynomials depending on integer variables, with quadratic monomials \(b^2_{i,j}(x_i - x_j)^2\)
• The quadratic Graver cone, quadratic integer minimization, and extensions
• A PTAS for the minimization of polynomials of fixed degree over the simplex

zbMATH Keywords

polynomial optimizationnonlinear integer programming

Mathematics Subject Classification ID

Nonlinear programming (90C30) Integer programming (90C10)

Cites Work

• On the Diophantine Equation mX 2 - nY 2 = ± 1
• Production Sets with Indivisibilities, Part I: Generalities
• Integer Polynomial Optimization in Fixed Dimension
• On the Computational Complexity of Determining the Solvability or Unsolvability of the Equation X 2 - DY 2 = -1
• Generalized convexity and optimization. Theory and applications
• Computing real roots of real polynomials
• On integer points in polyhedra
• Title not available (Why is that?)
• On the complexity of nonlinear mixed-integer optimization
• Mixed-integer quadratic programming is in NP
• Production Sets with Indivisibilities, Part II: The Case of Two Activities
• Integer optimization on convex semialgebraic sets
• Title not available (Why is that?)
• Mirror-Descent Methods in Mixed-Integer Convex Optimization

Cited In (9)

• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• Integer Polynomial Optimization in Fixed Dimension
• The efficient minimization of quadratic polynomials depending on integer variables, with quadratic monomials \(b^2_{i,j}(x_i - x_j)^2\)
• The quadratic Graver cone, quadratic integer minimization, and extensions
• Short Presburger Arithmetic Is Hard
• Complexity of optimizing over the integers
• Complexity aspects of local minima and related notions
• Integer quadratic programming in the plane
• A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)

This page was built for publication: Minimizing cubic and homogeneous polynomials over integers in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806816)