Subdeterminants and concave integer quadratic programming
From MaRDI portal
Publication:5206942
Abstract: We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by D in absolute value. The number of these integer linear programs is polynomial in the dimension n, in D and in 1/epsilon, provided that the number k of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with D at most two and k fixed. In the totally unimodular case D=1, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in 1/epsilon and is independent on n, provided that k is fixed.
Recommendations
- On approximation algorithms for concave mixed-integer quadratic programming
- On approximation algorithms for concave mixed-integer quadratic programming
- Proximity in concave integer quadratic programming
- The quadratic Graver cone, quadratic integer minimization, and extensions
- On simultaneous approximation in quadratic integer programming
Cites work
- A Class of Nonlinear Integer Programs Solvable by a Single Linear Program
- A cutting plane algorithm for solving bilinear programs
- A cutting plane algorithm for the bilinear programming problem
- A note on non-degenerate integer programs with small sub-determinants
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- A strongly polynomial algorithm for bimodular integer linear programming
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Algorithms for the single-source uncapacitated minimum concave-cost network flow problem
- An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra
- Approximation algorithms for indefinite quadratic programming
- Constrained global optimization: algorithms and applications
- Convex separable optimization is not much harder than linear optimization
- Decomposition of regular matroids
- FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
- Global Maximization of a Convex Function with Linear Inequality Constraints
- Global minimization of large-scale constrained concave quadratic problems by separable programming
- scientific article; zbMATH DE number 3121293 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 757677 (Why is no real title available?)
- scientific article; zbMATH DE number 3286662 (Why is no real title available?)
- scientific article; zbMATH DE number 970339 (Why is no real title available?)
- Integer Programming and Combinatorial Optimization
- Minimum concave cost flow over a grid network
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- Mixed-integer quadratic programming is in NP
- On approximation algorithms for concave mixed-integer quadratic programming
- On approximation algorithms for concave mixed-integer quadratic programming
- Some proximity and sensitivity results in quadratic integer programming
- The complexity of approximating a nonlinear program
- The Integrality Number of an Integer Program
- The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
Cited in
(9)- On approximation algorithms for concave mixed-integer quadratic programming
- A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization
- The quadratic Graver cone, quadratic integer minimization, and extensions
- Proximity in concave integer quadratic programming
- Integer programming in parameterized complexity: five miniatures
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Complexity of optimizing over the integers
- An approximation algorithm for indefinite mixed integer quadratic programming
- Convex quadratic sets and the complexity of mixed integer convex quadratic programming
This page was built for publication: Subdeterminants and concave integer quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5206942)
