A practical greedy approximation for the directed Steiner tree problem

被引:0
作者
Dimitri Watel
Marc-Antoine Weisser
机构
[1] CEDRIC-CNAM 292 rue Saint-Martin,LRI, CentraleSupélec
[2] Université Paris-Saclay,undefined
来源
Journal of Combinatorial Optimization | 2016年 / 32卷
关键词
Directed Steiner tree; Approximation algorithm; Greedy algorithm;
D O I
暂无
中图分类号
学科分类号
摘要
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ε)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(k^\varepsilon )$$\end{document}-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 GreedyFLAC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_\text {FLAC}$$\end{document} running in O(mlog(n)k+min(m,nk)nk2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(m \log (n)k + \min (m, nk)nk^2)$$\end{document} and a O(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\sqrt{k})$$\end{document}-approximation called GreedyFLAC▹\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_\text {FLAC}^\triangleright $$\end{document} running in O(nm+n2log(n)k+n2k3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(nm + n^2 \log (n)k +n^2 k^3)$$\end{document}. We provide computational results to show that, GreedyFLAC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_\text {FLAC}$$\end{document} rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.
引用
收藏
页码:1327 / 1370
页数:43
相关论文
共 37 条
  • [1] Byrka J(2013)Steiner tree approximation via iterative randomized rounding JACM 60 1-33
  • [2] Grandoni F(1999)Approximation algorithms for directed Steiner problems J Algorithm 33 73-91
  • [3] Rothvoss T(1979)A greedy heuristic for the set-covering problem Math Oper Res 4 233-235
  • [4] Sanità L(2001)Dual heuristics on the exact solution of large Steiner problems Electron Notes Discret Math 7 150-153
  • [5] Charikar M(2009)A distributed dual ascent algorithm for Steiner problems in multicast routing Networks 53 170-183
  • [6] Chekuri C(1998)A threshold of ln n for approximating set cover JACM 45 634-652
  • [7] Cheung T-Y(1962)Algorithm 97: shortest path Commun ACM 5 345-20
  • [8] Dai Z(2001)An improved approximation scheme for the group Steiner problem Networks 37 8-1425
  • [9] Goel A(2006)Fasterdsp: a faster approximation algorithm for directed Steiner tree problem J Inf Sci Eng 22 1409-145
  • [10] Guha S(1981)A fast algorithm for Steiner trees Acta inform 15 141-1164