---
id: "2026-11-10-graphic-tsp-89-64-gupta-sohrabi-tuncel-ai"
url: "https://postcutoff.com/e/2026-11-10-graphic-tsp-89-64-gupta-sohrabi-tuncel-ai/"
as_of: "2026-11-15T00:33:00+01:00"
date: "2026-11-10"
date_precision: day
category: science
importance: 4
confidence: medium
status: [Awaiting review]
verification: Preprint only
sources: 1
editor: human editor
human_review: null
version: null
---

As of: 2026-11-15 00:33 CET.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-11-10-graphic-tsp-89-64-gupta-sohrabi-tuncel-ai/

# Graphic TSP below 7/5 (89/64), GPT-5.6 Pro and GPT-6 Astra

Full title: Graphic TSP: Gupta, Sohrabi and Tunçel improve Sebő–Vygen's 7/5 approximation to 89/64 ≈ 1.3906, with counting arguments and parameter choices developed with GPT-5.6 Pro and GPT-6 Astra

arXiv 2611.13585 (10 Nov 2026), Swati Gupta, Mehrdad Sohrabi, Levent Tunçel: a polynomial-time algorithm returns a tour at most 89/64 = 7/5 − 3/320 times the subtour relaxation for graphic TSP, improving Sebő–Vygen's long-standing 7/5 and showing the subtour LP's integrality gap on graphic instances is at most 89/64. The AI methodology statement credits GPT-5.6 Pro with assistance on the counting and computations for the final bound in Section G, and GPT-6 Astra with refining the increase parameters and the convex-combination bounds in Appendix I.

## 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

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 194 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 133 days after its cutoff
- Gemini 4 Hydrogen (training cutoff March 2026): 224 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 163 days after its cutoff

## Sources

1. [arXiv 2611.13585: Approximating graphic TSP by b-matchings (Gupta, Sohrabi, Tunçel)](https://arxiv.org/abs/2611.13585) (arxiv.org, paper)

## Changes

- 2026-11-14 (filed): Created (science agent)

## Related

- 2026-11-14: [AI-assisted results, 14 Nov](https://postcutoff.com/e/2026-11-14-ai-assisted-results-november-14-listing/index.md)