Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design
verfasst von : Peng Zhang
Erschienen in: Combinatorial Optimization and Applications
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
The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio
$O(\sqrt{q})$
, where
q
is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number
q
(which is always at most
n
) is relatively small (say,
q
=
o
(log
2
n
)), our approximation ratio
$O(\sqrt q)$
is better than the currently known best ratio
O
(log
n
), where
n
is the number of vertices in the input graph.