An approximation algorithm for indefinite mixed integer quadratic programming
From MaRDI portal
Abstract: In this paper, we give an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P=NP. In order to design this algorithm we introduce the novel concepts of spherical form MIQP and of aligned vectors, and we provide a number of results of independent interest. In particular, we give a strongly polynomial algorithm to find a symmetric decomposition of a matrix, and show a related result on simultaneous diagonalization of matrices.
Recommendations
- On approximation algorithms for concave mixed-integer quadratic programming
- On approximation algorithms for concave mixed-integer quadratic programming
- Approximation algorithms for indefinite quadratic programming
- Subdeterminants and concave integer quadratic programming
- Approximation algorithm for a mixed binary quadratically constrained quadratic programming problem
Cites work
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra
- Approximation algorithms for indefinite quadratic programming
- Chvátal closures for mixed integer programming problems
- Convex separable optimization is not much harder than linear optimization
- FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 3677572 (Why is no real title available?)
- scientific article; zbMATH DE number 3790207 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Integer Programming
- Integer programming and incidence treedepth
- Integer Programming with a Fixed Number of Variables
- Integer quadratic programming in the plane
- Mathematics of public key cryptography.
- Mixed-integer quadratic programming is in NP
- Note on the complexity of the mixed-integer hull of a polyhedron
- On approximation algorithms for concave mixed-integer quadratic programming
- On approximation algorithms for concave mixed-integer quadratic programming
- On integer points in polyhedra
- Pivoting techniques for symmetric Gaussian elimination
- Polynomial time weak approximation algorithms for quadratic programming
- Quadratic programming is in NP
- Quadratic programming with one negative eigenvalue is NP-hard
- Some NP-complete problems in quadratic and nonlinear programming
- Some simplified NP-complete graph problems
- Subdeterminants and concave integer quadratic programming
- Systems of distinct representatives and linear algebra
- The complexity of approximating a nonlinear program
- The quadratic Graver cone, quadratic integer minimization, and extensions
Cited in
(10)- On approximation algorithms for concave mixed-integer quadratic programming
- On simultaneous approximation in quadratic integer programming
- scientific article; zbMATH DE number 6612550 (Why is no real title available?)
- On approximation algorithms for concave mixed-integer quadratic programming
- Computational study of a family of mixed-integer quadratic programming problems
- A simple effective heuristic for embedded mixed-integer quadratic programming
- Approximation algorithms for indefinite quadratic programming
- The mixed integer trust region problem
- Convex quadratic sets and the complexity of mixed integer convex quadratic programming
- Efficient local and tabu search strategies for large-scale general quadratic integer programming
This page was built for publication: An approximation algorithm for indefinite mixed integer quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165586)
