An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

2015/07/03 by Robert Hildebrand, Robert Weismantel, Hildebrand, Robert +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #FOS: Mathematics #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1507.00969

openalex publication_date 2015/07/03 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

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 Q x 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.

Related

• Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane
• An Approximation Algorithm for Indefinite Mixed Integer Quadratic Programming
• The Mixed Integer Trust Region Problem
• Harmonic Hierarchies for Polynomial Optimization
• Minimizing Polynomial Functions