An approximation algorithm for indefinite mixed integer quadratic programming

DOI10.1007/s10107-022-01907-3zbMath1522.90044arXiv2211.16442OpenAlexW4311111375MaRDI QIDQ6165586

Alberto Del Pia

Publication date: 1 August 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmpolynomial timesimultaneous diagonalizationmixed integer quadratic programmingsymmetric decomposition

Mathematics Subject Classification ID

Mixed integer programming (90C11) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mixed-integer quadratic programming is in NP
• Approximation algorithms for indefinite quadratic programming
• Chvátal closures for mixed integer programming problems
• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• Quadratic programming with one negative eigenvalue is NP-hard
• On integer points in polyhedra
• Geometric algorithms and combinatorial optimization
• Some simplified NP-complete graph problems
• Pivoting techniques for symmetric Gaussian elimination
• Note on the complexity of the mixed-integer hull of a polyhedron
• On approximation algorithms for concave mixed-integer quadratic programming
• The complexity of approximating a nonlinear program
• The quadratic Graver cone, quadratic integer minimization, and extensions
• Integer programming and incidence treedepth
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Quadratic programming is in NP
• Mathematics of Public Key Cryptography
• Integer Programming with a Fixed Number of Variables
• On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming
• Integer Programming
• Some NP-complete problems in quadratic and nonlinear programming
• An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra
• Subdeterminants and Concave Integer Quadratic Programming
• Integer quadratic programming in the plane
• Systems of distinct representatives and linear algebra
• Convex separable optimization is not much harder than linear optimization

This page was built for publication: An approximation algorithm for indefinite mixed integer quadratic programming