论文标题
分数分解树算法：研究整数程序的完整性差距的工具
Fractional Decomposition Tree Algorithm: A tool for studying the integrality gap of Integer Programs
论文作者
论文摘要
我们提出了一种新的算法，分数分解树（FDT），用于在所有变量都是二进制的情况下找到可行的整数程序（IP）的解决方案。 FDT在多项式时间内运行，并可以保证找到可行的整数解决方案，前提是完整性差距是界限的。该算法给出了Carr和Vempala定理的结构，即当通过实例完整性差距缩放时，对IP线性编程松弛的任何可行解决方案都占主导地位的可行解决方案的凸组合。 FDT也是研究IP公式的完整性差距的工具。我们证明，通过研究两个问题的完整性差距的实验：将树最佳地扩大到2边缘连接的图并找到最低成本2边缘连接的多毛图（2EC）。我们还提供了一种简化的算法DOM2IP，该算法更快地确定一个实例是否具有无限的完整性差距。我们表明，FDT的速度和近似质量与在顶点覆盖问题的中等大小实例上的可行性泵相提并论。对于一组特定的难以分解的分数2EC解决方案，FDT总是比最好的先前近似算法（Christofides）提供了更好的整数解决方案。
We present a new algorithm, Fractional Decomposition Tree (FDT) for finding a feasible solution for an integer program (IP) where all variables are binary. FDT runs in polynomial time and is guaranteed to find a feasible integer solution provided the integrality gap is bounded. The algorithm gives a construction for Carr and Vempala's theorem that any feasible solution to the IP's linear-programming relaxation, when scaled by the instance integrality gap, dominates a convex combination of feasible solutions. FDT is also a tool for studying the integrality gap of IP formulations. We demonstrate that with experiments studying the integrality gap of two problems: optimally augmenting a tree to a 2-edge-connected graph and finding a minimum-cost 2-edge-connected multi-subgraph (2EC). We also give a simplified algorithm, Dom2IP, that more quickly determines if an instance has an unbounded integrality gap. We show that FDT's speed and approximation quality compare well to that of feasibility pump on moderate-sized instances of the vertex cover problem. For a particular set of hard-to-decompose fractional 2EC solutions, FDT always gave a better integer solution than the best previous approximation algorithm (Christofides).
