论文标题
凹入整数二次编程的接近性
Proximity in Concave Integer Quadratic Programming
论文作者
论文摘要
Cook，Gerards，Schrijver和Tardos的经典结果在整数线性编程问题的最佳解决方案及其标准线性放松的最佳解决方案上提供了$Nδ$的上限。在此界限中，$ n $是变量的数量，$δ$表示约束矩阵子确定体的绝对值的最大值。 Hochbaum和Shanthikumar，Werman和Magagnosc表明，如果将更通用的凸函数最小化而不是线性函数，则相同的上限是有效的。当目标函数为非convex时，这种类型的接近结果均不知道。实际上，如果我们最大程度地减少了凹二次的二次，则无法给出$ n $和$δ$的函数。我们的主要观察结果是，在这种情况下，仍会发生接近现象，但前提是我们还考虑近似解决方案而不是最佳解决方案。在我们的主要结果中，我们为凹入整数二次编程问题和其连续放松的凹入整数二次编程问题和最佳（分别，近似）解决方案之间的距离提供了上限。我们的边界是$ n，δ$的函数，以及控制近似质量的参数$ε$。此外，我们讨论了我们的接近范围距离最佳距离。
A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of $n Δ$ on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, $n$ is the number of variables and $Δ$ denotes the maximum of the absolute values of the subdeterminants of the constraint matrix. Hochbaum and Shanthikumar, and Werman and Magagnosc showed that the same upper bound is valid if a more general convex function is minimized, instead of a linear function. No proximity result of this type is known when the objective function is nonconvex. In fact, if we minimize a concave quadratic, no upper bound can be given as a function of $n$ and $Δ$. Our key observation is that, in this setting, proximity phenomena still occur, but only if we consider also approximate solutions instead of optimal solutions only. In our main result we provide upper bounds on the distance between approximate (resp., optimal) solutions to a Concave Integer Quadratic Programming problem and optimal (resp., approximate) solutions of its continuous relaxation. Our bounds are functions of $n, Δ$, and a parameter $ε$ that controls the quality of the approximation. Furthermore, we discuss how far from optimal are our proximity bounds.
