An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra

DOI10.1137/1.9781611974331.CH118MaRDI QIDQ4575702zbMATH OpenOpenAlexFDO

Authors Robert Hildebrand, Robert Weismantel, Kevin Zemmer

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: We present a generic approach that allows us to develop a fully polynomial-time approximation scheme (FTPAS) for minimizing nonlinear functions over the integer points in a rational polyhedron in fixed dimension. The approach combines the subdivision strategy of Papadimitriou and Yannakakis (2000) with ideas similar to those commonly used to derive real algebraic certificates of positivity for polynomials. Our general approach is widely applicable. We apply it, for instance, to the Motzkin polynomial and to indefinite quadratic forms $x^{T}Qx$ in a fixed number of variables, where $Q$ has at most one positive, or at most one negative eigenvalue. In dimension three, this leads to an FPTAS for general $Q$.

Recommendations

• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• An FPTAS for minimizing the product of two non-negative linear cost functions
• An FPTAS for optimizing a class of low-rank functions over a polytope
• An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
• A PTAS for the minimization of polynomials of fixed degree over the simplex

Cited in

(12)

• On approximation algorithms for concave mixed-integer quadratic programming
• Subdeterminants and concave integer quadratic programming
• An FPTAS for minimizing the product of two non-negative linear cost functions
• Provable randomized rounding for minimum-similarity diversification
• An FPTAS for optimizing a class of low-rank functions over a polytope
• Short Presburger Arithmetic Is Hard
• Complexity of optimizing over the integers
• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• An approximation algorithm for indefinite mixed integer quadratic programming
• Electrical flows over spanning trees
• Integer programming in parameterized complexity: five miniatures
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization

This page was built for publication: An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra

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