论文标题
无限混合整数二次编程的近似算法
An Approximation Algorithm for Indefinite Mixed Integer Quadratic Programming
论文作者
论文摘要
在本文中，我们提供了一种算法，该算法找到了混合整数二次编程（MIQP）问题的Epsilon-Approximate解决方案。如果二次函数的等级和整数变量的数量固定，则该算法在多项式时间内运行。除非p = np，否则该算法的运行时间是可以预期的。为了设计这种算法，我们介绍了球形形式MIQP和对齐矢量的新颖概念，我们提供了许多独立兴趣的结果。特别是，我们给出了强烈的多项式算法，以找到矩阵的对称分解，并在同时对矩阵的对角线化时显示相关的结果。
In this paper, we give an algorithm that finds an epsilon-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.
