Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

详细信息    查看全文

• 作者：Tomoya Hibi ; Toshihiro Fujito
• 关键词：Approximation algorithms ; Steiner tree problem ; Directed graphs ; Greedy algorithm ; Tree cover problem
• 刊名：Algorithmica
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：74
• 期：2
• 页码：778-786
• 全文大小：393 KB
• 参考文献：1.Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. J. Algorithms 17(3), 381–408 (1994)CrossRef MathSciNet MATH
  2.Byrka, J., Grandoni, F., Rothvoss, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1–6:33 (2013)
  3.Calinescu, G., Zelikovsky, A.: The polymatroid Steiner problems. J. Comb. Optim. 9, 281–294 (2005)CrossRef MathSciNet MATH
  4.Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner tree problems. J. Algorithms 33, 73–91 (1999)CrossRef MathSciNet MATH
  5.Chlebík, M., Chlebíková, J.: The Steiner tree problem on graphs: inapproximability results. Theor. Comput. Sci. 406(3), 207–214 (2008)CrossRef MATH
  6.Feige, U.: A threshold of \(\ln n\) for approximating set cover. J. ACM 45(4), 634–652 (1998)CrossRef MathSciNet MATH
  7.Fujito, T.: How to trim a MST: a 2-approximation algorithm for minimum cost tree cover. ACM Trans. Algorithms 8(2), 16:1–16:11 (2012)CrossRef MathSciNet
  8.Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of the 35th Symposium on Theory of Computing, pp. 585–594. (2003)
  9.Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
  10.Karpinski, M., Zelikovsky, A.Z.: New approximation algorithms for the Steiner tree problem. J. Combin. Optim. 1, 47–65 (1997)CrossRef MathSciNet MATH
  11.Könemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved approximations for tour and tree covers. Algorithmica 38(3), 441–449 (2004)CrossRef MathSciNet MATH
  12.Konjevod, G.: Directed Steiner trees, linear programs and randomized rounding. Manuscript, 8 pages (2005)
  13.Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Appl. Math. 93, 265–285 (1999)CrossRef MathSciNet MATH
  14.Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: Proceedings of the 10th Symposium on Discrete Algorithms, pp. 742–751. (1999)
  15.Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Symposium on Theory of Computing, pp. 475–484. (1997)
  16.Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 122–134 (2005)CrossRef MathSciNet MATH
  17.Rothvoß, T.: Directed Steiner tree and the Lasserre hierarchy. arXiv:​1111.​5473 (2011)
  18.Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233–235 (1982)CrossRef MathSciNet MATH
  19.Zelikovsky, A.: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463–470 (1993)CrossRef MathSciNet MATH
  20.Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica 18, 99–110 (1997)CrossRef MathSciNet MATH
  21.Zosin, L., Khuller, S.: On directed Steiner trees. In: Proceedings of the 13th Symposium on Discrete Algorithms, pp. 59–63. (2002)
  
• 作者单位：Tomoya Hibi (1) (2)
  Toshihiro Fujito (1)
  
  1. Department of Computer Science and Engineering, Toyohashi University of Technology, Toyohashi, 441-8580, Japan
  2. NTT corporation, Kanagawa, Japan
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant \(l\), outputs a directed Steiner tree of cost no larger than \(2(l-1)(\ln n+1)\) times the cost of any \(l\)-restricted Steiner tree, which is such a Steiner tree in which every terminal is at most \(l\) arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of \(O(\log n)\), and (2) the tree cover problem on directed graphs can also be approximated within a factor of \(O(\log n)\). Keywords Approximation algorithms Steiner tree problem Directed graphs Greedy algorithm Tree cover problem