Maximum Entropy is a 10/7 Approximation Algorithm for the TSP on Half-Integral Cycle Cut Instances

Jul 16, 2026

Maximum Entropy is a 10/7-approximation algorithm for the Traveling Salesman Problem (TSP) on half-integral cycle cut instances. The work links integrality-gap properties of the Subtour LP relaxation to the performance of the maximum entropy spanning-tree rounding scheme. It identifies this instance class as containing examples where the Subtour LP has integrality gap at least 4/3, while also showing the max-entropy algorithm’s guarantee is at most 18/1, clarifying what tightness can and cannot be expected. The paper discusses why existing analysis does not yield improved integrality-gap bounds yet suggests potential directions for sharper analyses on other structured instances.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

Introduction

Traveling Salesman Problem and LP relaxation (Subtour LP)

Christofides–Serdyukov and its randomized variants

Maximum entropy distribution and performance guarantees

Maximum Entropy is a 10/7-Approximation Algorithm for the TSP on Half-Integral Cycle Cut Instances Billy Jin Purdue University Nathan Klein Boston University David P. Williamson Cornell University arXiv :2607 .0 1536v2 [ cs .DS] 3 Jul 2026 Abstract One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the Subtour LP relaxation of the TSP is equal to 43 . For 40 years, the best known upper bound was 1.5, due to Wolsey [Wol80] . Recently, Karlin, Klein, and Oveis Gharan [KKO22] showed that the max entropy algorithm for the TSP gives an improved bound of 1.5 − 10−36 . In this paper, we show that the maximum entropy algorithm is a 107-approximation for half-integral cycle cut instances of the TSP. This class of instances contains examples which demonstrate the subtour LP has an integrality gap of at least 43 , as well as examples showing that the performance of the max entropy algorithm is no better than 181 . We note that in [JKW23], the gap of this class of instances by 43 , authors gave an algorithm upper bounding the integrality so this work does not (and could not) provide an improved bound on the integrality gap. However, since there is no reason to believe that the analysis of the maximum entropy algorithm on general instances is tight, our work provides hope (and potentially direction) for improved analysis on other instance classes. 1 Introduction In the traveling salesman problem (TSP), we are given a set of n cities and the costs cij of traveling from city i to city j for all i, j. The goal of the problem is to find the cheapest tour that visits each city exactly once and returns to its starting point. An instance of the TSP is called symmetric if cij = cji for all i, j; it is asymmetric otherwise. Costs obey the triangle inequality (or are metric) if cij ≤ cik + ckj for all i, j, k. All instances we consider will be symmetric and obey the triangle inequality. We treat the problem input as a complete graph G = (V, E), where V is the set of cities, and ce = cij for edge e = {i, j} . In the mid-1970s, Christofides [Chr76] and Serdyukov [Ser78] each gave a 32-approximation algorithm for the symmetric TSP with triangle inequality. The algorithm computes a minimumcost spanning tree and then finds a minimum-cost perfect matching on the odd degree vertices of the tree to compute a connected Eulerian subgraph. Because the edge costs satisfy the triangle inequality, any Eulerian tour of this Eulerian subgraph can be “shortcut” to a tour of no greater cost. Until very recently, this was the best approximation factor known for the symmetric TSP with triangle inequality, although over the last decade substantial progress was made for many special cases and variants of the problem. In recent years, a variation on the Christofides-Serdyukov algorithm has been considered. Its starting point is a well-known linear programming relaxation of the TSP introduced by Dantzig, Fulkerson, and Johnson [DFJ54], sometimes called the Subtour LP or the Held-Karp bound [HK71] . The Subtour LP is as follows: min X c exe e∈E s.t. x (δ(v)) = 2, ∀ v ∈ V, (1) x (δ(S)) ≥ 2 , ∀ S ⊂ V, S ∅ , 0 ≤ xe ≤ 1 , ∀e ∈ E, where δ (S) is the set of all edges with exactly one endpoint in S and we use the shorthand that x (F ) = Pe∈F x e. Wolsey [Wol80] shows that the minimum-cost spanning tree is at most the value of the Subtour LP, and a matching on its odd degree vertices is at most half the value of the Subtour LP, showing that the Christofides-Serdyukov algorithm has cost at most 32 the Subtour LP. Following Wolsey, it is not difficult to show that for any solution x ∗ of this LP relaxation, ~~n~~−n1 x∗ is a feasible point in the spanning tree polytope, i.e., the convex hull of all spanning trees of the graph. Therefore, ~~n~~−n1 x∗ can be decomposed into a convex combination of spanning trees, and the cost of this convex combination is a lo

FAQs

What approximation factor does the paper prove for the maximum entropy algorithm on half-integral cycle cut instances?

The paper shows the maximum entropy algorithm achieves a 10/7 approximation ratio on half-integral cycle cut instances of the TSP.

What role does the Subtour LP (Held–Karp bound) play in the analysis?

The Subtour LP relaxation provides a benchmark through its integrality gap, and the spanning-tree rounding uses marginal constraints derived from an optimal LP solution.

Does this work improve known integrality-gap bounds for this instance class?

No. The paper notes that prior work already provides an upper bound on the integrality of this class, so the new analysis does not (and cannot) strengthen the integrality-gap bound, though it may guide improved analysis on other instance families.

Jul 16, 2026

Upload by Lucas Martin