On approximation algorithms for concave mixed-integer quadratic programming.

Concave mixed-integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an ϵ-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ϵ, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless P=NP. [ABSTRACT FROM AUTHOR]