 
[WW14] A practical greedy approximation for the Directed Steiner Tree problemConférence Internationale avec comité de lecture : Combinatorial optimization and applications (COCOA), November 2014, pp.200215, Series Lecture Notes in Computer Science, Wailea, Hawai, USA, (DOI: 10.1007/9783319126913_16)Mots clés: Directed Steiner Tree, Approximation algorithm, Greedy algorithm
Résumé:
The Directed Steiner Tree (DST) NPhard 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 kapproximation, 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 kapproximation 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 kapproximation and returns solution with smaller cost in practice.
Equipe:
oc
Collaboration:
Supélec
BibTeX

