TY - GEN
T1 - A (1 + ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
AU - Cohen, Nachshon
AU - Nutov, Zeev
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - 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 ⊆ E such that T ∪ F is 2-edge-connected. Tree Augmentation is equivalent to the problem of finding a minimum-cost edge-cover F ⊆ 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 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 solutions, which may be of independent interest.
AB - 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 ⊆ E such that T ∪ F is 2-edge-connected. Tree Augmentation is equivalent to the problem of finding a minimum-cost edge-cover F ⊆ 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 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 solutions, which may be of independent interest.
UR - http://www.scopus.com/inward/record.url?scp=80052368742&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22935-0_13
DO - 10.1007/978-3-642-22935-0_13
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:80052368742
SN - 9783642229343
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 147
EP - 157
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
Y2 - 17 August 2011 through 19 August 2011
ER -