|
 
|
[WW14] A practical greedy approximation for the Directed Steiner Tree problem
Conférence Internationale avec comité de lecture : Combinatorial optimization and applications (COCOA), November 2014, pp.200-215, Series Lecture Notes in Computer Science, Wailea, Hawai, USA, (DOI: 10.1007/978-3-319-12691-3_16)Mots clés: Directed Steiner Tree, Approximation algorithm, Greedy algorithm
Résumé:
The Directed Steiner Tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and $m$ arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a O(k^epsilon)-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give in this paper a new O(sqrt(k))-approximation greedy algorithm called greedy_FLAC_triangle, derived from a new fast k-approximation algorithm called greedy_FLAC running in time at most O(n m k^2).
We provide computational results to show that, greedy_FLAC rivals the running time of the fast k-approximation and returns solution with smaller cost in practice.
Equipe:
oc
Collaboration:
Supélec
BibTeX
| @inproceedings { | |||
| WW14, | |||
| title | = | "{A practical greedy approximation for the Directed Steiner Tree problem}", | |
| author | = | " D. Watel and M. Weisser ", | |
| booktitle | = | "{Combinatorial optimization and applications (COCOA)}", | |
| year | = | 2014, | |
| month | = | "November", | |
| series | = | "Lecture Notes in Computer Science", | |
| pages | = | "200-215", | |
| address | = | "Wailea, Hawai, USA", | |
| doi | = | "10.1007/978-3-319-12691-3_16", | |
| } | |||
