pith. sign in

arxiv: 2607.01536 · v1 · pith:3AR62TR2new · submitted 2026-07-01 · 💻 cs.DS

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

Billy Jin , Nathan Klein , David P. Williamson This is my paper

Pith reviewed 2026-07-03 17:36 UTC · model grok-4.3

classification 💻 cs.DS
keywords traveling salesman problemmaximum entropy algorithmsubtour LPapproximation algorithmsintegrality gaphalf-integral solutionscycle cut instances
0
0 comments X

The pith

The maximum entropy algorithm is a 10/7-approximation for the TSP on half-integral cycle cut instances.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the maximum entropy algorithm for the traveling salesman problem achieves a 10/7 approximation ratio on half-integral cycle cut instances. These instances include cases where the subtour LP has an integrality gap of at least 4/3 and where the algorithm performs no better than 11/8. The result supplies a tighter guarantee than the general 3/2 bound even though a separate argument already shows the integrality gap of the class is at most 4/3.

Core claim

The maximum entropy algorithm is a 10/7-approximation for half-integral cycle cut instances of the TSP. This class contains examples demonstrating that the subtour LP has integrality gap at least 4/3, as well as examples showing that the performance of the max entropy algorithm is no better than 11/8.

What carries the argument

The maximum entropy algorithm, which samples a spanning tree from the maximum-entropy distribution consistent with a given subtour LP solution and then augments it to a tour.

If this is right

  • The maximum entropy algorithm improves from its general 3/2 bound to a 10/7 bound on this entire class.
  • The 10/7 guarantee continues to hold on instances that realize the 4/3 integrality-gap lower bound for the subtour LP.
  • The result supplies no improvement to the known 4/3 upper bound on the integrality gap of the class itself.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The structural restrictions of half-integral cycle cut instances may be reusable to obtain tighter ratios for the maximum entropy algorithm on wider families of TSP instances.
  • The gap between the 10/7 guarantee and the 11/8 worst-case examples within the class indicates that further local analysis of the sampling distribution could close the remaining distance.
  • Because the class already forces the subtour LP gap to 4/3, any future improvement to the maximum entropy analysis on this class would have to come from the algorithm rather than from the LP itself.

Load-bearing premise

The input instance must be a half-integral cycle cut instance, so its subtour LP solution is half-integral and satisfies the cycle-cut condition.

What would settle it

A half-integral cycle cut instance on which the tour returned by the maximum entropy algorithm has cost strictly greater than 10/7 times the subtour LP value.

Figures

Figures reproduced from arXiv: 2607.01536 by Billy Jin, David P. Williamson, Nathan Klein.

Figure 1
Figure 1. Figure 1: Edges and tight sets at the root node r. promising that max entropy, while not able to obtain the 4 3 ratio of [JKW25a] (which is specialized to these instances), is nonetheless able to simulate that algorithm with a relatively small loss in approximation ratio. It remains an interesting open question to close the gap in the performance guarantee of the maximum entropy algorithm between the lower bound of … view at source ↗
Figure 2
Figure 2. Figure 2: Edges and tight sets at non-root node S. formally.3 If V − {r} is partitioned into two tight sets A and B with edges {e, f} = δ(r)∩δ(A) and {g, h} = δ(r)∩δ(B), then the maximum entropy algorithm selects exactly one edge from {e, f} and one from {g, h} independently and uniformly at random. For the two edges {a, b} = δ(A) ∩ δ(B) joining any pair of sets in the tree T that are children of a tight set S in th… view at source ↗
read the original 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 $\frac{4}{3}$. For 40 years, the best known upper bound was $1.5$, due to Wolsey. Recently, Karlin, Klein, and Oveis Gharan 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 $\frac{10}{7}$-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 $\frac{4}{3}$, as well as examples showing that the performance of the max entropy algorithm is no better than $\frac{11}{8}$. We note that in the authors recently gave an algorithm upper bounding the integrality gap of this class of instances by $\frac{4}{3}$, 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that the maximum entropy algorithm for the TSP yields a 10/7-approximation on half-integral cycle cut instances. This class includes instances achieving the 4/3 integrality gap of the subtour LP as well as instances where the max-entropy algorithm performs no better than 11/8. The authors observe that a separate recent result by the same authors already bounds the integrality gap of the class by 4/3, so the contribution is an improved algorithmic analysis rather than a new gap bound.

Significance. If the 10/7 bound holds, the result supplies a concrete, better-than-1.5 analysis of the max-entropy algorithm on a non-trivial subclass that contains the known worst-case examples for the subtour LP. It thereby supplies evidence that the general 1.5-10^{-36} analysis is not tight and offers a potential template for tightening the analysis on other structured instance families.

minor comments (1)
  1. [Abstract] Abstract, final paragraph: the sentence beginning 'We note that in the authors recently gave' contains a grammatical error and should be rephrased (e.g., 'The authors recently gave').

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the result, and recommendation of minor revision. The report accurately captures the contribution as an improved algorithmic analysis (rather than a new integrality-gap bound) on a class containing both the 4/3-gap examples and 11/8-performance examples for max-entropy. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity; approximation guarantee is a theorem derived from algorithm analysis on the instance class

full rationale

The paper claims to prove that the maximum entropy algorithm achieves a 10/7 approximation ratio on half-integral cycle cut instances, a result presented as following from the algorithm's properties and the structural assumptions of the instance class (half-integrality plus cycle-cut condition). No equations, fitted parameters, or self-referential definitions are visible in the abstract or description that would reduce the 10/7 factor to an input by construction. The reference to prior work bounding the integrality gap by 4/3 is explicitly noted as unrelated to improving that gap and does not serve as a load-bearing justification for the 10/7 claim. The derivation is therefore self-contained as a standard approximation proof rather than matching any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the definition of the half-integral cycle cut class and on the known properties of the maximum entropy distribution; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The maximum entropy algorithm produces a distribution over tours whose expected cost is bounded relative to the subtour LP value.
    Standard property of the algorithm used in the cited prior work.

pith-pipeline@v0.9.1-grok · 5785 in / 1285 out tokens · 31690 ms · 2026-07-03T17:36:47.857481+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 4 canonical work pages

  1. [1]

    Applegate and Robert E

    David L. Applegate and Robert E. Bixby and Va s ek Chv \'a tal and William J. Cook. The Traveling Salesman Problem: A Computational Study

  2. [2]

    Goemans and Aleksander Mądry and Shayan Oveis Gharan and Amin Saberi

    Arash Asadpour and Michel X. Goemans and Aleksander Mądry and Shayan Oveis Gharan and Amin Saberi. An O ( n/ n) -Approximation Algorithm for the Asymmetric Traveling Salesman Problem

  3. [3]

    Finding the exact integrality gap for small traveling salesman problems

    Genevi\`eve Benoit and Sylvia Boyd. Finding the exact integrality gap for small traveling salesman problems

  4. [4]

    51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages =

    Gurvits, Leonid and Klein, Nathan and Leake, Jonathan , title =. 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.ICALP.2024.79 , annote =

    work page doi:10.4230/lipics.icalp.2024.79 2024

  5. [5]

    Finding Low Cost TSP and 2-matching Solutions Using Certain Half-Integer Subtour Vertices

    Sylvia Boyd and Robert Carr. Finding Low Cost TSP and 2-matching Solutions Using Certain Half-Integer Subtour Vertices. Discrete Optimization

  6. [6]

    Structure of Extreme Points of the Subtour Elimination Polytope of the STSP

    Sylvia Boyd and Paul Elliott-Magwood. Structure of Extreme Points of the Subtour Elimination Polytope of the STSP. RIMS K\^ o ky\^ u roko Besstsu

  7. [7]

    Boyd and W.R

    S.C. Boyd and W.R. Pulleyblank. Optimizing over the subtour polytope of the travelling salesman problem

  8. [8]

    The Salesman's Improved Tours for Fundamental Classes

    Sylvia Boyd and Andr\'as Seb o. The Salesman's Improved Tours for Fundamental Classes

  9. [9]

    New Results on the Old k - OPT Algorithm for the Traveling Salesman Problem

    Barun Chandra and Howard Karloff and Craig Tovey. New Results on the Old k - OPT Algorithm for the Traveling Salesman Problem

  10. [10]

    Worst Case Analysis of a New Heuristic for the Traveling Salesman Problem

    Nicos Christofides. Worst Case Analysis of a New Heuristic for the Traveling Salesman Problem

  11. [11]

    Cornuejols and G

    G. Cornuejols and G. L. Nemhauser. Tight Bounds for Christofides' Traveling Salesman Heuristic

  12. [12]

    Williamson

    Kyle Genova and David P. Williamson. An Experimental Evaluation of the Best-of-Many C hristofides' Algorithm for the Traveling Salesman Problem

  13. [13]

    Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP

  14. [14]

    Matroid-Based TSP Rounding for Half-Integral Solutions

    Anupam Gupta and Euiwoong Lee and Jason Li and Marcin Mucha and Heather Newman and Sherry Sarkar. Matroid-Based TSP Rounding for Half-Integral Solutions. Integer Programming and Combinatorial Optimization

  15. [15]

    27th Annual European Symposium on Algorithms (ESA 2019) , pages =

    Arash Haddadan and Alantha Newman , title =. 27th Annual European Symposium on Algorithms (ESA 2019) , pages =. 2019 , volume =

    2019

  16. [16]

    Michael Held and Richard M. Karp. The Traveling-Salesman Problem and Minimum Spanning Trees

  17. [17]

    Williamson

    Billy Jin and Nathan Klein and David P. Williamson. A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. Integer Programming and Combinatorial Optimization

  18. [18]

    Williamson

    Billy Jin and Nathan Klein and David P. Williamson. A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP

  19. [19]

    Williamson

    Billy Jin and Nathan Klein and David P. Williamson. A Lower Bound for the Maximum Entropy Algorithm for TSP

  20. [20]

    Removing and Adding Edges for the Traveling Salesman Problem

  21. [21]

    A Randomized Rounding Approach to the Traveling Salesman Problem

    Shayan Oveis Gharan and Amin Saberi and Mohit Singh. A Randomized Rounding Approach to the Traveling Salesman Problem

  22. [22]

    Papadimitriou and Umesh V

    Christos H. Papadimitriou and Umesh V. Vazirani. On Two Geometric Problems Related to the Travelling Salesman Problem

  23. [23]

    Rosenkrantz and Richard E

    Daniel J. Rosenkrantz and Richard E. Stearns and Philip M. Lewis II. An Analysis of Several Heuristics for the Traveling Salesman Problem

  24. [24]

    Williamson and Anke

    Frans Schalekamp and David P. Williamson and Anke. 2-Matchings, the Traveling Salesman Problem, and the Subtour

  25. [25]

    Shorter Tours By Nicer Ears: 7/5-Approximation for the Graph-

    Andr\'as Seb. Shorter Tours By Nicer Ears: 7/5-Approximation for the Graph-

  26. [26]

    Serdyukov

    A. Serdyukov. On Some Extremal Walks in Graphs. Upravlyaemye Sistemy

  27. [27]

    Shmoys and David P

    David B. Shmoys and David P. Williamson. Analyzing the H eld- K arp TSP Bound: A Monotonicity Property with Application

  28. [28]

    L. A. Wolsey. Heuristic Analysis, Linear Programming and Branch and Bound. Mathematical Programming Study

  29. [29]

    On the Approximation Ratio of k - Opt and L in- K ernighan Algorithm

    Xianghui Zhong. On the Approximation Ratio of k - Opt and L in- K ernighan Algorithm

  30. [30]

    Karlin and Nathan Klein and Shayan

    Anna R. Karlin and Nathan Klein and Shayan. An Improved Approximation Algorithm for

  31. [31]

    Karlin and N

    A. Karlin and N. Klein and S. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , title =. 2022 , volume =

    2022

  32. [32]

    and Klein, Nathan and

    Karlin, Anna R. and Klein, Nathan and. A (Slightly) Improved Approximation Algorithm for Metric TSP , journal =. 2024 , doi =. https://doi.org/10.1287/opre.2022.2338 , abstract =

    work page doi:10.1287/opre.2022.2338 2024

  33. [33]

    Mathematical Programming , year=

    Gupta, Anupam and Lee, Euiwoong and Li, Jason and Mucha, Marcin and Newman, Heather and Sarkar, Sherry , title=. Mathematical Programming , year=. doi:10.1007/s10107-024-02065-4 , url=

    work page doi:10.1007/s10107-024-02065-4

  34. [34]

    Dinits and A.V

    E.A. Dinits and A.V. Karzanov and M.V. Lomonosov , Date-Added =. Studies in Discrete Mathematics (in Russian), ed. A.A. Fridman, 290-306, Nauka (Moskva) , Title =

  35. [35]

    A quick proof for the cactus representation of mincuts , Year =

    Fleiner, Tam. A quick proof for the cactus representation of mincuts , Year =

  36. [36]

    Dantzig and R

    G. Dantzig and R. Fulkerson and S. Johnson , journal =. Solution of a Large-Scale Traveling-Salesman Problem , urldate =

  37. [37]

    Approximation, Randomization, and Combinatorial Optimization

    Klein, Nathan and Taziki, Mehrshad , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) , pages =. 2025 , volume =. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.21 , annote =

    work page doi:10.4230/lipics.approx/random.2025.21 2025