Subdeterminants and Concave Integer Quadratic Programming
From MaRDI portal
Publication:5206942
DOI10.1137/18M121873XzbMath1461.90075arXiv1810.02763OpenAlexW2996066982WikidataQ126589313 ScholiaQ126589313MaRDI QIDQ5206942
Publication date: 19 December 2019
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.02763
approximation algorithmconcave functioninteger quadratic programmingtotal unimodularitysubdeterminantstotal bimodularity
Integer programming (90C10) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (4)
Proximity in concave integer quadratic programming ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Complexity of optimizing over the integers ⋮ An approximation algorithm for indefinite mixed integer quadratic programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Mixed-integer quadratic programming is in NP
- Approximation algorithms for indefinite quadratic programming
- Some proximity and sensitivity results in quadratic integer programming
- FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
- Constrained global optimization: algorithms and applications
- Decomposition of regular matroids
- Algorithms for the single-source uncapacitated minimum concave-cost network flow problem
- A note on non-degenerate integer programs with small sub-determinants
- On approximation algorithms for concave mixed-integer quadratic programming
- The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
- The complexity of approximating a nonlinear program
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- Minimum concave cost flow over a grid network
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming
- Global minimization of large-scale constrained concave quadratic problems by separable programming
- Global Maximization of a Convex Function with Linear Inequality Constraints
- A cutting plane algorithm for solving bilinear programs
- A cutting plane algorithm for the bilinear programming problem
- A Class of Nonlinear Integer Programs Solvable by a Single Linear Program
- An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra
- A strongly polynomial algorithm for bimodular integer linear programming
- The Integrality Number of an Integer Program
- Integer Programming and Combinatorial Optimization
- Convex separable optimization is not much harder than linear optimization
This page was built for publication: Subdeterminants and Concave Integer Quadratic Programming