[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


@inproceedings {
title="{A practical greedy approximation for the Directed Steiner Tree problem}",
author=" D. Watel and M. Weisser ",
booktitle="{Combinatorial optimization and applications (COCOA)}",
series="Lecture Notes in Computer Science",
address="Wailea, Hawai, USA",