A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius. (English) Zbl 1294.05146
Summary: We consider the Tree Augmentation problem: given a graph \(G=(V,E)\) with edge-costs and a tree \(T\) on \(V\) disjoint to \(E\), find a minimum-cost edge-subset \(F\subseteq E\) such that \(T\cup F\) is 2-edge-connected. Tree Augmentation is equivalent to the problem of finding a minimum-cost edge-cover \(F\subseteq E\) of a laminar set-family. The best known approximation ratio for Tree Augmentation is 2, even for trees of radius 2. As laminar families play an important role in network design problems, obtaining a better ratio is a major open problem in connectivity network design. We give a \((1+\ln 2)\)-approximation algorithm for trees of constant radius. Our algorithm is based on a new decomposition of problem feasible solutions, and on an extension of Steiner Tree technique of Zelikovsky to the Set-Cover problem, which may be of independent interest.
Keywords:
tree augmentation; edge-connectivity; laminar family; local replacement; approximation algorithmsReferences:
| [2] | Cheriyan, J.; Karloff, H.; Khandekar, R.; Könemann, J., On the integrality ratio for tree augmentation, Operations Research Letters, 36, 4, 399-401 (2008) · Zbl 1155.90466 |
| [3] | Even, G.; Kortsarz, G.; Nutov, Z., A 1.5 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2, Information Processing Letters, 111, 6, 296-300 (2011) · Zbl 1260.68464 |
| [4] | Fredrickson, G. N.; Jájá, J., On the relationship between the biconnectivity augmentation and traveling salesman problem, Theorethical Computer Science, 19, 2, 189-201 (1982) · Zbl 0486.90082 |
| [5] | Goemans, M.; Williamson, D., The primal dual method for approximation algorithms and its applications to network design problems, (Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1995), PWS), 144-191, (Chapter 4) |
| [6] | Jain, K., A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica, 21, 1, 39-60 (2001) · Zbl 1107.68533 |
| [7] | Khuller, S., Approximation algorithms for for finding highly connected subgraphs, (Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1995), PWS), 236-265, (Chapter 6) |
| [8] | Kortsarz, G.; Nutov, Z., Approximating minimum cost connectivity problems, (Gonzales, T. F., Approximation Algorithms and Metahueristics (2007), CRC), (Chapter 58) |
| [9] | Maduel, Y.; Nutov, Z., Covering a laminar family by leaf to leaf links, Discrete Applied Mathematics, 158, 13, 1424-1432 (2010) · Zbl 1209.05049 |
| [10] | Nagamochi, H., An approximation for finding a smallest 2-edge connected subgraph containing a specified spanning tree, Discrete Applied Mathematics, 126, 83-113 (2003) · Zbl 1012.68226 |
| [11] | Schrijver, A., Combinatorial Optimization, Polyhedra and Efficiency (2004), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York · Zbl 1072.90030 |
| [12] | Zelikovsky, Alexander, Better approximation bounds for the network and euclidean steiner tree problems. Technical report (1995) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
