Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius
verfasst von : Nachshon Cohen, Zeev Nutov
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.