| Article ID: | iaor2009698 |
| Country: | Netherlands |
| Volume: | 36 |
| Issue: | 1 |
| Start Page Number: | 1 |
| End Page Number: | 3 |
| Publication Date: | Jan 2008 |
| Journal: | Operations Research Letters |
| Authors: | Shmoys David B., Schalekamp Frans |
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(log