A practical greedy approximation for the Directed Steiner Tree problem

摘要: The Directed Steiner Tree (DST) NP-hard problem asks, considering a directed weighted graph with \(n\) nodes and \(m\) arcs, node \(r\) called root set of \(k\) \(X\) terminals, for minimum cost tree rooted at spanning \(X\). best known polynomial approximation ratio DST is \(O(k^\varepsilon )\)-approximation greedy algorithm. However, much faster \(k\)-approximation, returning the shortest paths from to \(X\), generally used in practice. We give this paper new \(O(\sqrt{k})\)-approximation algorithm Greedy\(_\mathrm{FLAC }\) \(^\triangleright \), derived fast \(k\)-approximation running time most \(O(n m k^2)\).