Metric TSP approximation frontier

Approximation guarantees and hardness for metric traveling salesman under the triangle inequality.

Specification version 1Published 2026-08-271 evidence records

What we know

Current frontiers derived from accepted Claims.

PROVEN LOWER BOUNDBEST KNOWN UPPER BOUND

UNKNOWN GAP

3/2 − ε

Proven lower boundGap: UnknownBest known upper bound

Claims

Assertions tied to evidence, attribution, and review.

2026

CLM-LR-DRAFT-TSP-1<= 3/2 − εUPPER BOUNDA (slightly) improved approximation algorithm for metric TSPEvidence: 1 linked source records

SOURCE CONFIRMED

Timeline

The frontier as it changed over time.

How this frontier is derived

Only accepted Claims matching the current specification contribute to the displayed bounds. Strict inequalities remain open; contradictory Claims require editorial review.

—No breakthrough events recorded yetEvents appear here when an accepted Claim tightens a bound or closes the frontier.

Specification

What question is being asked?

Approximation guarantees and hardness for metric traveling salesman under the triangle inequality.

Constraints: problem=metric TSP · assumption=P ≠ NP for hardness claim

Read full specification ↗

Corrections & disputes

Record history

No unresolved corrections or disputes are recorded for this published version.

View timeline ↗

Editorial status

Evidence-backed record

1 accepted Claim, with 1 linked evidence records.

Human-reviewed · No AI-only claims

Verified prizes & bounties

Active verified incentives

No active verified bounties are linked to this Limit.

View verified bounty tracker ↗

Reproducibility

Machine-checked history

No accepted machine-checked reproductions are recorded for this Limit.

Cite this LimitLimits Registry. LR-DRAFT-TSP. Metric TSP approximation frontier. 2026.