Approximating 1-dimensional TSP Requires Omega(n log n) Comparisons
Skip to main content
eScholarship
Open Access Publications from the University of California
Refine Search

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

Approximating 1-dimensional TSP Requires Omega(n log n) Comparisons

Published Web Location

https://arxiv.org/pdf/1303.2920
No data is associated with this publication.
Abstract

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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item

 

 

 


Top