The Directed Orienteering Problem

The Directed Orienteering Problem

0.00 Avg rating0 Votes
Article ID: iaor20115153
Volume: 60
Issue: 4
Start Page Number: 1017
End Page Number: 1030
Publication Date: Aug 2011
Journal: Algorithmica
Authors: ,
Keywords: programming: travelling salesman
Abstract:

This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k‐TSP problem: given an asymmetric metric (V,d), a root rV and a target k≤|V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time O ( log 2 n log log n log k ) equ1 ‐approximation algorithm for this problem. We use this algorithm for directed k‐TSP to obtain an O ( log 2 n log log n ) equ2 ‐approximation algorithm for the directed orienteering problem. This answers positively, the question of poly‐logarithmic approximability of directed orienteering, an open problem from Blum et al. (2007). The previously best known results were quasi‐polynomial time algorithms with approximation guarantees of O(log 2 k) for directed k‐TSP, and O(log n) for directed orienteering (2005). Using the algorithm for directed orienteering within the framework of Blum et al. (2007) and Bansal et al. (2004), we also obtain poly‐logarithmic approximation algorithms for the directed versions of discounted‐reward TSP and vehicle routing problem with time‐windows.

Reviews

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