Approximation algorithms for metric tree cover and generalized tour and tree covers
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 305-315.

Given a weighted undirected graph G=(V,E), a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of G. Arkin, Halldórsson and Hassin (1993) give approximation algorithms with factors respectively 3.5 and 5.5. Later Könemann, Konjevod, Parekh, and Sinha (2003) study the linear programming relaxations and improve both factors to 3. We describe in the first part of the paper a 2-approximation algorithm for the metric case of tree cover. In the second part, we will consider a generalized version of tree (resp. tour) covers problem which is to find a minimum tree (resp. tours) which covers a subset D⊆E of G. We show that the algorithms of Könemann et al. can be adapted for the generalized tree and tours covers problem with the same factors.

DOI : 10.1051/ro:2007025
Classification : 90C27, 90C59
Mots-clés : approximation algorithms, graph algorithms, network design 
@article{RO_2007__41_3_305_0,
     author = {Nguyen, Viet Hung},
     title = {Approximation algorithms for metric tree cover and generalized tour and tree covers},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {305--315},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {3},
     year = {2007},
     doi = {10.1051/ro:2007025},
     mrnumber = {2348005},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2007025/}
}
TY  - JOUR
AU  - Nguyen, Viet Hung
TI  - Approximation algorithms for metric tree cover and generalized tour and tree covers
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2007
SP  - 305
EP  - 315
VL  - 41
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2007025/
DO  - 10.1051/ro:2007025
LA  - en
ID  - RO_2007__41_3_305_0
ER  - 
%0 Journal Article
%A Nguyen, Viet Hung
%T Approximation algorithms for metric tree cover and generalized tour and tree covers
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 305-315
%V 41
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2007025/
%R 10.1051/ro:2007025
%G en
%F RO_2007__41_3_305_0
Nguyen, Viet Hung. Approximation algorithms for metric tree cover and generalized tour and tree covers. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 305-315. doi : 10.1051/ro:2007025. http://www.numdam.org/articles/10.1051/ro:2007025/

[1] E.M. Arkin, M.M. Halldórsson and R. Hassin, Approximating the tree and tour covers of a graph. Inf. Process. Lett. 47 (1993) 275-282. | Zbl

[2] J. Edmonds, Optimum branchings. J. Res. Nat. Bur. Stand. B 71 (1965). | MR | Zbl

[3] M.R. Garey and D.S. Johnson, Computer and Intractablity: A Guide to the theory of the NP-Completeness, Freeman (1978). | MR | Zbl

[4] M.X. Goemans and D.J. Bertsimas, Survivable networks, linear programming relaxations and the parsinomious property. Math. Program. 60 (1993) 145-166. | Zbl

[5] Y.J. Chu and T.H. Liu, On the shortest arborescence of a directed graph. Scientia Sinica 14 (1965). | MR | Zbl

[6] J. Könemann, G. Konjevod, O. Parekh and A. Sinha, Improved approximations for tour and tree covers. Algorithmica 38 (2003) 441-449. | Zbl

[7] D.B. Shmoys and D.P. Williamsons, Analyzing the help-karp tsp bound: a monotonicity property with application. Inf. Process. Lett. 35 (1990) 281-285. | Zbl

[8] V.V. Vazirani and S. Rajagopalan, On the bidirected cut relaxation for metric bidirected steiner tree problem, in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (1999) 742-751. | Zbl

[9] L.A. Wolsey, Heuristic analysis, linear programming and branch-and-bound. Math. Program. Stud. 13 (1980) 121-134. | Zbl

Cité par Sources :