|
|||||
|
|
Algorithms for the universal and a priori TSP |
|
| Authors: | Frans Schalekamp David B Shmoys |
| Institution: | School of ORIE, Cornell University, 288 Rhodes Hall, Ithaca, NY 14853, USA |
| Abstract: | We present two simple results for generalizations of the traveling salesman problem (TSP): for the universal TSP, we show that one can compute a tour that is universally optimal whenever the input is a tree metric. A (randomized) O(logn)-approximation algorithm for the a priori TSP follows as a corollary. |
| Keywords: | Traveling salesman problem A priori optimization Universal optimization Metric embedding |
| 本文献已被 ScienceDirect 等数据库收录！ | |