Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

详细信息    查看全文

• 作者：Tomoya Hibi (20)
  Toshihiro Fujito (20)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7551
• 期：1
• 页码：225-236
• 全文大小：192KB
• 参考文献：1. Byrka, J., Grandoni, F., Rothvo?, T., Sanità, L.: An improved LP-based approximation for Steiner tree. In: Proc. 42nd STOC, pp. 583-92 (2010)
  2. Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. In: Proc. 3rd SODA, pp. 325-34 (1992)
  3. Chlebík, M., Chlebíková, J.: The Steiner tree problem on graphs: Inapproximability results. Theory Comput. Syst.?406(3), 207-14 (2008) CrossRef
  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-1 (1999) CrossRef
  5. Calinescu, G., Zelikovsky, A.: The polymatroid Steiner problems. J. Comb. Opt.?9, 281-94 (2005) CrossRef
  6. Feige, U.: A threshold of ln / n for approximating set cover. J. ACM?45(4), 634-52 (1998) CrossRef
  7. Fujito, T.: How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.?4051, pp. 431-42. Springer, Heidelberg (2006) CrossRef
  8. Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proc. 35th STOC, pp. 585-94 (2003)
  9. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85-03. Plenum Press, New York (1972) CrossRef
  10. Karpinski, M., Zelikovsky, A.Z.: New approximation algorithms for the Steiner tree problem. J. Comb. Opt.?1, 47-5 (1997) CrossRef
  11. K?nemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved Approximations for Tour and Tree Covers. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.?1913, pp. 184-93. Springer, Heidelberg (2000) CrossRef
  12. Konjevod, G.: Directed Steiner trees, linear programs and randomized rounding, 8 pages (2005) (manuscript)
  13. Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Applied Mathematics?93, 265-85 (1999) CrossRef
  14. Nguyen, V.H.: Approximation Algorithm for the Minimum Directed Tree Cover. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part II. LNCS, vol.?6509, pp. 144-59. Springer, Heidelberg (2010) CrossRef
  15. Rothvo?, T.: Directed Steiner tree and the Lasserre hierarchy. ArXiv e-prints (November 2011)
  16. Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th STOC, pp. 475-84 (1997)
  17. Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: Proc. 10th SODA, pp. 742-51 (1999)
  18. Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math.?19, 122-34 (2005) CrossRef
  19. Savage, C.: Depth-first search and the vertex cover problem. Inform. Process. Lett.?14(5), 233-35 (1982) CrossRef
  20. Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica?18, 99-10 (1997) CrossRef
  21. Zelikovsky, A.: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica?9, 463-70 (1993) CrossRef
  22. Zosin, L., Khuller, S.: On directed Steiner trees. In: Proc. 13th SODA, pp. 59-3 (2002)
  
• 作者单位：Tomoya Hibi (20)
  Toshihiro Fujito (20)
  
  20. Department of Computer Science and Engineering, Toyohashi University of Technology, Tempaku, Toyohashi, 441-8580, Japan
  

文摘

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??-)(ln n--) times the cost of the minimum l-restricted Steiner tree. 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(logn), and 2) the tree cover problem on directed graphs can also be approximated within a factor of O(logn).