A practical greedy approximation for the directed Steiner tree problem

Dimitri Watel () and Marc-Antoine Weisser ()
Additional contact information
Dimitri Watel: CEDRIC-CNAM 292 rue Saint-Martin
Marc-Antoine Weisser: Université Paris-Saclay

Journal of Combinatorial Optimization, 2016, vol. 32, issue 4, No 20, 1327-1370

Abstract: 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 )$$ O ( k ε ) -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}$$ FLAC running in $$O(m \log (n)k + \min (m, nk)nk^2)$$ O ( m log ( n ) k + min ( m , n k ) n k 2 ) and a $$O(\sqrt{k})$$ O ( k ) -approximation called Greedy $$_\text {FLAC}^\triangleright $$ FLAC ▹ running in $$O(nm + n^2 \log (n)k +n^2 k^3)$$ O ( n m + n 2 log ( n ) k + n 2 k 3 ) . We provide computational results to show that, Greedy $$_\text {FLAC}$$ FLAC rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.

Keywords: Directed Steiner tree; Approximation algorithm; Greedy algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0074-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:4:d:10.1007_s10878-016-0074-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0074-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().