An Improved Lower Bound for the Traveling Salesman Constant

Julia Gaudio, Patrick Jaillet

Let $X_1,X_2,\dots ,X_n$ be independent uniform random variables on $[0,1{]}^2$. Let $L(X_1,\dots ,X_n)$ be the length of the shortest Traveling Salesman tour through these points…