标题： 旅行推销员问题的整数性间隙为$4/3$，如果 LP 解最多有$n+6$个非零分量 显示英文标题

标题： The Integrality Gap of the Traveling Salesman Problem is $4/3$ if the LP Solution Has at Most $n+6$ Non-zero Components

摘要： 在本文中，我们研究了度量旅行商问题的经典Dantzig-Fulkerson-Johnson公式，并探讨其线性松弛的整数性间隙，即子环消除问题（SEP）。 这个整数性间隙被猜想为$4/3$。 我们证明，当在$n$个节点上求解一个问题时，如果最优SEP解最多有$n+6$个非零分量，则该猜想成立。 为了建立这一结果，我们考虑给定整数$k$的无限族$F_k$，该族收集了所有SEP多面体对于$n \in \mathbb{N}$的顶点中恰好具有$n+k$个非零分量的顶点。 然后，我们介绍一种将$F_k$的描述简化为有限集合的过程，并提出 Gap-Bounding 算法，该算法为整个家族$F_k$提供可证明的整数间隙上界。 Gap-Bounding 算法应用于$k \leq 6$会产生一个计算机辅助证明，表明该猜想的界限在这种情况成立。 显示英文摘要

摘要： In this paper, we address the classical Dantzig-Fulkerson-Johnson formulation of the 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 consider, for a given integer $k$, the infinite family $F_k$ which gathers, among all the vertices of all the SEP polytopes for $n \in \mathbb{N}$, the ones with exactly $n+k$ non-zero components. Then, we introduce a procedure that reduces the description of $F_k$ to a finite set, and we present the Gap-Bounding algorithm, which provides provable upper bounds on the integrality gap for entire families $F_k$. The application of the Gap-Bounding algorithm for $k \leq 6$ yields a computer-aided proof that the conjectured bound holds in this case.