Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Hardness and approximation results for packing steiner trees

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Θ(m 1/3/−ɛ) and give an approximation guarantee ofO(m 1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Arora and C. Lund, Hardness of approximations, inApproximation Algorithms for NP-Hard Problems, D. Hochbaum, ed., PWS, Boston, MA, 1996.

    Google Scholar 

  2. A. Baveja and A. Srinivasan, Approximation algorithms for disjoint paths and related routing and packing problems,Mathematics of Operations Research 25:255–280, 2000. Earlier version in FOCS 1997.

    Article  MATH  MathSciNet  Google Scholar 

  3. R. Carr and S. Vempala, Randomized metarounding,Random Structures and Algorithms, 20:343–352, 2002. Earlier version in STOC 2000.

    Article  MATH  MathSciNet  Google Scholar 

  4. M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, Approximation algorithms for directed Steiner problem,Journal of Algorithms 33(1):73–91, 1999. Earlier version in SODA 1998.

    Article  MATH  MathSciNet  Google Scholar 

  5. M. Charikar, J. Naor, and B. Schieber, Resource optimization in QoS multicast routing of real-time multimedia,Proc. 19thAnnual IEEE INFOCOM, pp. 1518–1527, 2000.

  6. J. Cheriyan and M.R. Salavatipour, Packing element-disjoint Steiner trees, Manuscript, 2004.

  7. M. Chlebík and J. Chlebíková, Inapproximability results for bounded variants of optimization problems,Proc. 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), pp. 27–38, LNCS 2751, Springer, Berlin, 2003.

    Google Scholar 

  8. R. Diestel,Graph Theory, Springer, New York, 2000.

    Google Scholar 

  9. U. Feige, M. Halldorsson, G. Kortsarz, and A. Srinivasan, Approximating the domatic number,SIAM Journal on Computing 32(1):172–195, 2002. Earlier version in STOC 2000.

    Article  MATH  MathSciNet  Google Scholar 

  10. P. Floréen, P. Kaski, J. Kohonen, and P. Orponen, Multicast time maximization in energy constrained wireless networks,Proc. 2003Joint Workshop on Foundations of Mobile Computing (DIALM-POMC2003), San Diego, CA, pp. 50–58, 2003.

  11. S. Fortune, J. Hopcroft, and J. Wyllie, The directed subgraph homeomorphism problem,Theoretical Computer Science 10(2):111–121, 1980.

    Article  MATH  MathSciNet  Google Scholar 

  12. A. Frank, T. Király, and M. Kriesell, On decomposing a hypergraph intok connected sub-hypergraphs,Discrete Applied Mathematics 131(2):373–383, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  13. M. Grötschel, A. Martin, and R. Weismantel, The Steiner tree packing problem in VLSI design,Mathematical Programming 78:265–281, 1997.

    Article  MathSciNet  Google Scholar 

  14. S. Guha and S. Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets,Information and Computation 150:57–74, 1999. Earlier version in FST&TCS 1998.

    Article  MathSciNet  Google Scholar 

  15. V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems,Journal of Computer and System Sciences 67(3):473–496, 2003. Earlier version in STOC 1999.

    Article  MATH  MathSciNet  Google Scholar 

  16. E. Hazan, S. Safra, and O. Schwartz, On the hardness of approximatingk-dimensional matching, Electronic Colloqium on Computational Complexity, Rep. No. 20, 2003.

  17. K. Jain, M. Mahdian, and M.R. Salavatipour, Packing Steiner trees,Proc. SODA 2003, pp. 266–274.

  18. V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete,Information Processing Letters 37:27–35, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  19. P. Kaski, Packing Steiner trees with identical terminal sets,Information Processing Letters 91(1):1–5, 2004.

    Article  MathSciNet  Google Scholar 

  20. P.N. Klein and R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees,Journal of Algorithms 19(1):104–114, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  21. S.G. Kolliopoulos and C. Stein, Approximating disjoint-path problems using packing integer programs,Mathematical Programming 99:63–87, 2004. Earlier version in Proc. IPCO 1998.

    Article  MATH  MathSciNet  Google Scholar 

  22. M. Kriesell, Edge-disjoint trees containing some given vertices in a graph,Journal of Combinatorial Theory. Series B 88:53–65, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  23. L. Lau, An approximate max-Steiner-tree-packing min-Steiner-cut theorem,Proc. 45thIEEE FOCS, pp. 61–70, 2004.

  24. A. Martin and R. Weismantel, Packing paths and Steiner trees: routing of electronic circuits,CWI Quarterly 6:185–204, 1993.

    MATH  MathSciNet  Google Scholar 

  25. S. Vempala, and B. Vöcking, Approximating multicast congestion,Proc. 10th ISAAC, Chennai, pp. 367–372, LNCS 1741, Springer, Berlin, 1999.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada

    Joseph Cheriyan

  2. Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada

    Mohammad R. Salavatipour

Authors
  1. Joseph Cheriyan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammad R. Salavatipour
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joseph Cheriyan.

Additional information

Supported by NSERC Grant No. OGP0138432.

Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and a University start-up fund at University of Alberta.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cheriyan, J., Salavatipour, M.R. Hardness and approximation results for packing steiner trees. Algorithmica 45, 21–43 (2006). https://doi.org/10.1007/s00453-005-1188-4

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-005-1188-4

Key Words

Search

Navigation