Integer Polynomial Optimization in Fixed Dimension

Abstract

We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are non-negative over the polytope, these sequences of bounds lead to a fully polynomial-time approximation scheme for the optimization problem.

In this revised version we include a stronger complexity bound on our algorithm. Our algorithm is in fact an FPTAS (fully polynomial-time approximation scheme) to maximize a non-negative integer polynomial over the lattice points of a polytope

References in corpus (1)

• Convex Combinatorial Optimization

Cited by in corpus (10)

• Nonlinear Integer Programming
• A primal Barvinok algorithm based on irrational decompositions
• Pareto Optima of Multicriteria Integer Linear Programs
• Rational Generating Functions and Integer Programming Games
• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• Local Euler-Maclaurin formula for polytopes
• Scheduling for a Processor Sharing System with Linear Slowdown
• A Factorisation Algorithm in Adiabatic Quantum Computation
• Weighted Ehrhart Theory: Extending Stanley's nonnegativity theorem
• A polynomial algorithm for minimizing discrete convic functions in fixed dimension