An approximation algorithm for indefinite mixed integer quadratic programming

• 成果类型: Article
• 署名作者: Del Pia, Alberto
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01907-3
• 发表日期: 2023
• 页码: 263-293
• 关键词: minimization; POLYNOMIALS; complexity; points

摘要

In this paper, we give an algorithm that finds an e-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P=NP. In order to design this algorithm we introduce the novel concepts of spherical form MIQP and of aligned vectors, and we provide a number of results of independent interest. In particular, we give a strongly polynomial algorithm to find a symmetric decomposition of a matrix, and show a related result on simultaneous diagonalization of matrices.