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 $$epsilon $$ ? -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/epsilon $$ 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 $$mathcal {P}=mathcal {NP}$$ P = NP .