摘要
组合优化领域最著名的猜想之一是四分之三猜想，声称TSP的子巡回LP松弛的整数间隙等于 $\frac{4}{3}$。在过去的40年中，已知的最佳上界为1.5，由Wolsey提出。最近，Karlin、Klein和Oveis Gharan展示了最大熵算法为TSP提供了一个改进的上界，达到 $1.5 - 10^{-36}$。
在本文中，我们证明最大熵算法对TSP的半整数循环割实例是一个 $\frac{10}{7}$ 的近似算法。这类实例包含一些示例，展示子巡回LP具有至少 $\frac{4}{3}$ 的整数间隙，以及一些示例表明最大熵算法的性能不优于 $\frac{11}{8}$。我们注意到，作者最近给出了一个算法，将这一类实例的整数间隙上界限制在 $\frac{4}{3}$，因此这项工作并没有（也不可能）提供对整数间隙的改进上界。
然而，由于没有理由相信对一般实例的最大熵算法分析是紧的，我们的工作为其他实例类别的改进分析提供了希望（和潜在方向）。
博主点评： 本文通过最大熵算法在特定TSP实例上取得了重要进展，尽管未能进一步缩小整数间隙，但为未来的研究提供了新的方向，显示了组合优化领域的深厚潜力。