  


Subdeterminants and Concave Integer Quadratic Programming
Alberto Del Pia (delpiawisc.edu) Abstract: We consider the NPhard 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 epsilonapproximate 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 polynomialtime 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  