Bertsimas–Grigni universal TSP lower-bound conjecture on the plane
Let be the unit square with the Euclidean metric. For a linear order on , let denote its TSP order ratio function.
Bertsimas–Grigni conjecture. For every linear order on the unit square,
This conjecture asserts that every universal traveling-salesman ordering on the planar unit square has logarithmically growing worst-case competitive ratio. The paper establishes the lower bound for every linear order, but does not resolve the conjectured logarithmic bound.
References
- Cosmas Kravaris, “Lower bounds for the universal TSP on the plane”, arXiv:2412.16448 (2026).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.