Given a directed graph G with non-negative cost on the arcs, a directed tour cover T of G is a cycle (not necessarily simple) in G such that either head or tail (or both of them) of every arc in G is touched by T. The minimum directed tour cover problem (DToCP), which is to find a directed tour cover of minimum cost, is NP-hard. It is thus interesting to design approximation algorithms with performance guarantee to solve this problem. Although its undirected counterpart (ToCP) has been studied in recent years, in our knowledge, the DToCP remains widely open. In this paper, we give a 2 log2( n)-approximation algorithm for the DToCP.
References
[1]
Arkin, E.M.; Halldórsson, M.M.; Hassin, R. Approximating the tree and tour covers of a graph. Inf. Pro. Lett. 1993, 47, 275–282.
[2]
K？nemann, J.; Konjevod, G.; Parekh, O.; Sinha, A. Improved Approximations for Tour and Tree Covers. Algorithmica 2003, 38, 441–449.
[3]
Kaplan, H.; Lewenstein, M.; Shafrir, N.; Sviridenko, M. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 2005, 52, 602–626.
[4]
Frieze, A.M.; Galbiati, G.; Maffioli, F. On the worst case performance of some algorithms for the asymmetric traveling salesman problem. Networks 1982, 12, 23–39.
[5]
Williamson, D.P. Analysis of the Held-Karp heuristic for the traveling salesman problem. M.D. Thesis, Massachusettes Institute of Technology, Cambridge, MA, USA, 1990.
[6]
Goemans, M.X.; Bertsimas, D.J. On the parsimonious property of connectivity problems. Proceeding of the First Annual ACM-SIAM Symposimum on Discrete Algorithm; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 1990; pp. 388–396.
[7]
Lovasz, L. On some connectivity properties of Eulerian graphs. Acta Mathematica Hungarica 1976, 28, 129–138.
[8]
Jackson, B. Some remarks on arc-connectivity, vertex splitting, and orientation in graphs and digraphs. J. Graph Theory 1988, 12, 429–436.
[9]
Asadpour, A.; Goemans, M.X.; Madry, A.; Oveis Gharan, S.; Saberi, A. An O(log n/log log n)–approximation algorithm for the asymmetric traveling salesman problem. Procceding of 21st ACM-SIAM Symposium on Discrete Algorithms; 2010.
