31 citations · 38 across the 5 of their papers we have counts for
1 paper · 1 filter
Neal E. Young
We give a short proof that any comparison-based n^(1-epsilon)-approximation algorithm for the 1-dimensional Traveling Salesman Problem (TSP) requires Omega(n log n) comparisons.