Bertsimas–Grigni universal TSP lower-bound conjecture on the plane
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.