A practical greedy approximation for the directed Steiner tree problem |
| |
Authors: | Dimitri Watel Marc-Antoine Weisser |
| |
Institution: | 1.CEDRIC-CNAM 292 rue Saint-Martin,Paris Cédex 03,France;2.LRI, CentraleSupélec,Université Paris-Saclay,Orsay Cedex,France |
| |
Abstract: | 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^\varepsilon )\)-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy\(_\text {FLAC}\) running in \(O(m \log (n)k + \min (m, nk)nk^2)\) and a \(O(\sqrt{k})\)-approximation called Greedy\(_\text {FLAC}^\triangleright \) running in \(O(nm + n^2 \log (n)k +n^2 k^3)\). We provide computational results to show that, Greedy\(_\text {FLAC}\) rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|