Bertsimas–Grigni universal TSP lower-bound conjecture on the plane

Let $([0,1]^2,\lVert\cdot\rVert_2)$ be the unit square with the Euclidean metric. For a linear order $\leq$ on $[0,1]^2$, let $OR_{\leq}(n)$ denote its TSP order ratio function.

Bertsimas–Grigni conjecture. For every linear order $\leq$ on the unit square,

$$OR_{\leq}(n) \gtrsim \log n.$$

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 $OR_{\leq}(n) \gtrsim \sqrt{\log n/\log\log n}$ for every linear order, but does not resolve the conjectured logarithmic bound.