Optimization Online


Subdeterminants and Concave Integer Quadratic Programming

Alberto Del Pia (delpia***at***wisc.edu)

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.

Keywords: integer quadratic programming, approximation algorithm, concave function, subdeterminants, total unimodularity, total bimodularity

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Global Optimization (Theory )

Citation: Manuscript

Download: [PDF]

Entry Submitted: 04/23/2018
Entry Accepted: 04/23/2018
Entry Last Modified: 08/28/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society