The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components
Tullio Villa, Eleonora Vercesi, Janos Barta, Monaldo Mastrolilli
我们解决了经典的Dantzig - Fulkerson - Johnson对称度量旅行推销员问题的公式,并研究其线性放松的积分差距,即亚图消除问题(SEP)。 这种整体性差距被推测为4/3。 我们证明,在解决 n 个节点上的问题时,如果最优的 SEP 解决方案最多有 n + 6 个非零组件,那么猜想是正确的。 为了建立这一结果,我们设计了一种新的方法,结合了理论分析和计算验证。
We address the classical Dantzig - Fulkerson - Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution has at most n + 6 non-zero components, then the conjecture is true. To establish this result, we devise a new methodology that combines theoretical analysi...
