|
 
|
[LBG15] An approximation algorithm for packing Steiner trees under budget and delay constraints
Conférence Internationale avec comité de lecture : EURO, July 2015, pp.1, UK,
motcle:
Résumé:
Given a network with, for each edge, a capacity, a delay, and a cost, we consider the problem of fractionally packing Steiner trees under capacity, budget, and delay constraints. This kind of problem arises in telecommunication applications, where one wishes to send as much information as possible to a set of clients through a network, while ensuring a given level of quality of service and under a given budget constraint. Steiner tree problems naturally appear in the framework of multicast routing, where any node in the network is allowed to replicate its input data to release an information flow on its outputs. In this paper, we extend existing models of Steiner trees packing by incorporating budget and delay constraints. We first formalize this problem, then we give an approximation algorithm inspired by the method proposed by Garg and K\"onemann which solve it, provided its dual separation problem can be approximated. Hence, we obtain complexity and approximation results for several special cases of our packing problem.
\keywords{Approximation algorithm, Steiner trees fractional packing, multicast routing.
Equipe:
oc
Collaboration:
BibTeX
| @inproceedings { | |||
| LBG15, | |||
| title | = | "{An approximation algorithm for packing Steiner trees under budget and delay constraints}", | |
| author | = | " T. Lefebvre and C. Bentz and E. Gourdin ", | |
| booktitle | = | "{EURO}", | |
| year | = | 2015, | |
| month | = | "July", | |
| pages | = | "1", | |
| address | = | " UK", | |
| } | |||
