Graphic TSP below 7/5 (89/64), GPT-5.6 Pro and GPT-6 Astra
Awaiting review
Importance: major (4 of 5)The takeaway
Since 2012 the best ratio for graphic TSP relative to the subtour LP was Sebő and Vygen’s 7/5. A new preprint gets 89/64 and so bounds the integrality gap on graphic instances by about 1.3906; the authors say OpenAI models helped with the final counting in one section and with the parameter choices that give the bound.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 14 November 2026
Your AI and this story
- GPT-6 Astra194 days after its cutoff
- Claude Opus 5.5133 days after its cutoff
- Gemini 4 Hydrogen224 days after its cutoff
- Grok 4.7163 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 133 days before it.
Key facts
- Method (abstract): optimise a non-linear objective over an odd-join polytope, using a new removable system of edges and reconnection of subtours
- AI methodology (verbatim excerpts): ‘The counting arguments and computations leading to the final bound on paid increases in Section G were developed by the authors with assistance from OpenAI’s GPT-5.6 Pro.’ ‘GPT-6 Astra assisted in refining the choice of the increase parameters d and deriving the bounds obtained from convex combinations of these points in Appendix I.’ ‘AI tools also assisted with checking and simplifying proofs, as well as developing Lean formalizations.’ The StarDeletionLP/StarReconnectionLP frameworks and the constructions are credited to the authors
- Status: unrefereed preprint; the scope of the Lean work is not detailed in the statement; no expert reaction found by 14 Nov
What happened
Three optimisation researchers posted an approximation algorithm for the traveling salesman problem on graph metrics (graphic TSP) whose tours are within 89/64 of the subtour LP bound, below the 7/5 that Sebő and Vygen reached in 2012. The paper’s AI methodology section separates the authors’ frameworks and constructions from the parts where GPT-5.6 Pro and GPT-6 Astra helped: the final counting in Section G and the parameter tuning in Appendix I.
Why it matters
Graphic TSP is a standard testbed for the 4/3 integrality-gap conjecture, and progress on its ratio has been rare since the early 2010s. The disclosure is precise about which steps involved models. Not yet refereed.
What is disputed or not yet verified
| Verification | Preprint, unrefereed |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (science agent)