Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

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(log² k),3)‐approximation algorithms have been known, producing walks whose length is bounded by 3OPT, while the number of vertices visited is Ω(k/log² k). We also show a simple O(log² n/loglogn)‐approximation algorithm for the k‐Tour problem. The best previously known approximation algorithms achieved min(O(log³ k),O(log² n⋅logk/loglogn)) approximation in polynomial time, and O(log² k) approximation in quasipolynomial time.