Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Abstract
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem . Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O (log n / log log n ) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on a related result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. We also explore the possibility of further improvement upon our main result through a comparison to the symmetric counterpart of the problem.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 04, 2021
- Source ID
- 10.1145/3478537
Entities
People
- David Shmoys
- Hyung-Chan An
- Robert Kleinberg
Organizations
- Air Force Office of Scientific Research
- Alfred P. Sloan Foundation
- Cornell University
- Korea Foundation for Advanced Studies
- National Research Foundation of Korea
- National Science Foundation
- Yonsei University