2005 | OriginalPaper | Buchkapitel
Packing Trees in Communication Networks
verfasst von : Mohamed Saad, Tamás Terlaky, Anthony Vannelli, Hu Zhang
Erschienen in: Internet and Network Economics
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
Given an undirected edge-capacitated graph and a collection of subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each spanning a given subset of vertices without violating the capacity constraints. We give an integer linear programming (ILP) formulation, and observe that its linear programming (LP-) relaxation is a fractional packing problem with exponentially many variables and with a block (sub-)problem that cannot be solved in polynomial time. To this end, we take an
r
-approximate block solver to develop a (1 −
ε
)/
r
approximation algorithm for the LP-relaxation. The algorithm has a polynomial coordination complexity for any
ε
∈ (0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only approximate block solvers and a coordination complexity that is polynomial in the input size and
ε
− 1
. This leads to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is also to be assigned one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths.