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

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

0.00 Avg rating0 Votes
Article ID: iaor20131263
Volume: 65
Issue: 3
Start Page Number: 545
End Page Number: 561
Publication Date: Mar 2013
Journal: Algorithmica
Authors: ,
Keywords: combinatorial optimization
Abstract:

We consider two natural generalizations of the Asymmetric Traveling Salesman problem: the kStroll and the kTour problems. The input to the kStroll 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 st walk, containing at least k distinct vertices (including the endpoints s,t). The kTour problem can be viewed as a special case of kStroll, where s=t. That is, the walk is required to be a tour, containing some pre‐specified vertex s. When k=n, the kStroll problem becomes equivalent to Asymmetric Traveling Salesman Path, and kTour to Asymmetric Traveling Salesman. Our main result is a polylogarithmic approximation algorithm for the kStroll 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 kTour 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.

Reviews

Required fields are marked *. Your email address will not be published.