On approximation algorithms for concave mixed-integer quadratic programming

• 成果类型: Article
• 署名作者: Del Pia, Alberto
• 署名单位: University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1178-8
• 发表日期: 2018
• 页码: 3-16
• 关键词: points; np; minimization; POLYNOMIALS; dimension; polyhedra

摘要

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.