Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
Venue
Algorithmica, vol. 65 (2013), pp. 545-561
Publication Year
2013
Authors
Mohammadhossein Bateni, Julia Chuzhoy
BibTeX
Abstract
We consider two natural generalizations of the Asymmetric Traveling Salesman
problem: the k-Stroll and the k-Tour problems. The input to the k-Stroll problem is
a directed n-vertex graph with nonnegative edge lengths, an integer k, as well as
two special vertices s and t. The goal is to find a minimum-length s-t walk,
containing at least k distinct vertices (including the endpoints s,t). The k-Tour
problem can be viewed as a special case of k-Stroll, where s=t. That is, the walk
is required to be a tour, containing some pre-specified vertex s. When k=n, the
k-Stroll problem becomes equivalent to Asymmetric Traveling Salesman Path, and
k-Tour to Asymmetric Traveling Salesman. Our main result is a polylogarithmic
approximation algorithm for the k-Stroll problem. Prior to our work, only
bicriteria (O(log2 k),3)-approximation algorithms have been known, producing walks
whose length is bounded by 3OPT, while the number of vertices visited is ?(k/log2
k). We also show a simple O(log2 n/loglogn)-approximation algorithm for the k-Tour
problem. The best previously known approximation algorithms achieved min(O(log3
k),O(log2 n?logk/loglogn)) approximation in polynomial time, and O(log2 k)
approximation in quasipolynomial time.
