An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra

DOI10.1137/1.9781611974331.CH118zbMATH Open1411.68191arXiv1507.00969OpenAlexW2950038749MaRDI QIDQ4575702FDOQ4575702

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)

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$.

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

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

Mathematics Subject Classification ID

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

Cited In (12)

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

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)