New Bounds for the Euclidean TSP Constant
The Beardwood-Halton-Hammersley theorem characterizes the asymptotic length of the optimal Euclidean traveling salesman tour through independent and uniformly distributed random points $X_1,\ldots,X_n$ in the unit square. It states that there exists a universal constant $β$ such that the length of the shortest tour is asymptotic to $β\sqrt{n}$ almost surely. The best bounds established to date are $0.6277\leq β\leq 0.90367$. In this paper, we improve these bounds to $0.6421\leqβ\leq0.8810$. Using importance sampling, we further show that $0.6536\leq β\leq 0.8749$ holds with probability at…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.02809
curl -X POST /api/v1/records/arxiv/2610.02809/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.02809/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'