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

An Efficient Approximation Algorithm for the Steiner Tree Problem

  • Chapter
  • First Online:
Complexity and Approximation

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12000))

  • 985 Accesses

Abstract

Given an arbitrary weighted graph, the Steiner tree problem seeks a minimum-cost tree spanning a given subset of the vertices (terminals). Byrka et al. proposed an interactive method that achieves an approximation ratio of \(1.3863+\epsilon \). Moreover, Goemans et al. shown that it is possible to achieve the same approximation guarantee while only solving hypergraphic LP relaxation once. However, solving hypergraphic LP relaxation is time consuming. This article presents an efficient two-phase heuristic in greedy strategy that achieves an approximation ratio of 1.4295.

This article appeared in 2019 the 2nd International Conference on Information Science and Systems (ICISS), under the title “An Efficient Approximation Algorithm for the Steiner Tree Problem”.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 54.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 69.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput. 24(3), 440–456 (1995)

    Article  MathSciNet  Google Scholar 

  2. Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for prize-collecting steiner tree and TSP. SIAM J. Comput. 40(2), 309–332 (2011)

    Article  MathSciNet  Google Scholar 

  3. Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)

    Article  MathSciNet  Google Scholar 

  4. Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(5), 21:1–21:37 (2011)

    Article  MathSciNet  Google Scholar 

  5. Berman, P., Karpinski, M., Zelikovsky, A.: 1.25-approximation algorithm for steiner tree problem with distances 1 and 2. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 86–97. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03367-4_8

    Chapter  MATH  Google Scholar 

  6. Berman, P., Ramaiyer, V.: Improved approximations for the steiner tree problem. J. Algorithms 17(3), 381–408 (1994)

    Article  MathSciNet  Google Scholar 

  7. Bern, M., Plassmann, P.: The steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4), 171–176 (1989)

    Article  MathSciNet  Google Scholar 

  8. Borchers, A., Du, D.Z.: The k-steiner ratio in graphs. SIAM J. Comput. 26(3), 857–869 (1997)

    Article  MathSciNet  Google Scholar 

  9. Byrka, J., Grandoni, F., Rothvoss, T., Sanitá, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1–6:33 (2013)

    Article  MathSciNet  Google Scholar 

  10. Caldwell, A.E., Kahng, A.B., Mantik, S., Markov, I.L., Zelikovsky, A.: On wirelength estimations for row-based placement. In: ISPD 1998: Proceedings of the 1998 International Symposium on Physical Design, pp. 4–11. ACM, New York, NY, USA (1998)

    Google Scholar 

  11. Chen, Y.H., Lu, C.L., Tang, C.Y.: On the full and bottleneck full steiner tree problems. In: Warnow, T., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 122–129. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45071-8_14

    Chapter  Google Scholar 

  12. Chen, Y.H.: An improved approximation algorithm for the terminal steiner tree problem. In: Murgante, B., Gervasi, O., Iglesias, A., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2011, Part III. LNCS, vol. 6784, pp. 141–151. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21931-3_12

    Chapter  Google Scholar 

  13. Chlebík, M., Chlebíková, J.: The steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci. 406(3), 207–214 (2008). Algorithmic Aspects of Global Computing

    Article  MathSciNet  Google Scholar 

  14. Demaine, E.D., Hajiaghayi, M., Klein, P.N.: Node-weighted steiner tree and group steiner tree in planar graphs. ACM Trans. Algorithms 10(3), 13:1–13:20 (2013)

    Article  MathSciNet  Google Scholar 

  15. Drake, D.E., Hougardy, S.: On approximation algorithms for the terminal steiner tree problem. Inf. Process. Lett. 89(1), 15–18 (2004)

    Article  MathSciNet  Google Scholar 

  16. Feldmann, A.E., Könemann, J., Olver, N., Sanità, L.: On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree. Math. Program. 160(1), 379–406 (2016)

    Article  MathSciNet  Google Scholar 

  17. Ferreira, C.E., de Oliveira Filho, F.M.: New reduction techniques for the group steiner tree problem. SIAM J. Optim. 17(4), 1176–1188 (2006)

    Article  MathSciNet  Google Scholar 

  18. Fuchs, B.: A note on the terminal steiner tree problem. Inf. Process. Lett. 87(4), 219–220 (2003)

    Article  MathSciNet  Google Scholar 

  19. Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H. Freeman, New York (2002)

    Google Scholar 

  20. Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp. 253–259. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1998)

    Google Scholar 

  21. Goemans, M.X., Olver, N., Rothvoß, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic steiner tree relaxations. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing,TOC 2012, pp. 1161–1176. ACM, New York, NY, USA (2012)

    Google Scholar 

  22. Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., Wang, N.: Integrality ratio for group Steiner trees and directed steiner trees. SIAM J. Comput. 36(5), 1494–1511 (2007)

    Article  MathSciNet  Google Scholar 

  23. Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 585–594. ACM, New York, NY, USA (2003)

    Google Scholar 

  24. Hougardy, S., Prömel, H.J.: A 1.598 approximation algorithm for the Steiner problem in graphs. In: SODA 1999: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 448–453. Society for Industrial and Applied Mathematics, Philadelphia, ACM, New York (1999)

    Google Scholar 

  25. Hsieh, S.Y., Gao, H.M.: On the partial terminal Steiner tree problem. J. Supercomput. 41(1), 41–52 (2007)

    Article  Google Scholar 

  26. Hsieh, S.-Y., Gao, H.-M., Yang, S.-C.: On the internal Steiner tree problem. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 274–283. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72504-6_25

    Chapter  Google Scholar 

  27. Huang, C.W., Lee, C.W., Gao, H.M., Hsieh, S.Y.: The internal Steiner tree problem: hardness and approximations. J. Complex. 29(1), 27–43 (2013)

    Article  MathSciNet  Google Scholar 

  28. Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. Annuals of Discrete Mathematics, vol. 53. Elsevier Science Publishers, Amsterdam (1992)

    MATH  Google Scholar 

  29. Kahng, A.B., Robins, G.: On Optimal Interconnections for VLSI. Kluwer Academic, Boston (1995)

    Book  Google Scholar 

  30. Karpinski, M., Zelikovsky, A.: New approximation algorithms for the Steiner tree problems. J. Comb. Optim. 1, 47–65 (1997)

    Article  MathSciNet  Google Scholar 

  31. Korte, B., Prömel, H.J., Steger, A.: Steiner trees in VLSI-layout. Paths, Flows, and VLSI-Layout, pp. 185–214 (1990)

    Google Scholar 

  32. Liang, W.: Constructing minimum-energy broadcast trees in wireless ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2002, pp. 112–122. ACM, New York, NY, USA (2002)

    Google Scholar 

  33. Lin, G.H., Xue, G.L.: On the terminal steiner tree problem. Inf. Process. Lett. 84(2), 103–107 (2002)

    Article  MathSciNet  Google Scholar 

  34. Lu, C.L., Tang, C.Y., Lee, R.C.T.: The full Steiner tree problem. Theor. Comput. Sci. 306(1–3), 55–67 (2003)

    Article  MathSciNet  Google Scholar 

  35. Martinez, F.V., de Pina, J.C., Soares, J.: Algorithms for terminal Steiner trees. J. Theor. Comput. Sci. 389(1—-2), 133–142 (2007)

    Article  MathSciNet  Google Scholar 

  36. Min, M., Du, H., Jia, X., Huang, C.X., Huang, S.C.H., Wu, W.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Glob. Optim. 35(1), 111–119 (2006)

    Article  MathSciNet  Google Scholar 

  37. Prömel, H.J., Steger, A.: RNC-approximation algorithms for the steiner problem. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 559–570. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0023489

    Chapter  Google Scholar 

  38. Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19(1), 122–134 (2005)

    Article  MathSciNet  Google Scholar 

  39. Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Jpn. 24, 573–577 (1980)

    MathSciNet  MATH  Google Scholar 

  40. Zelikovsky, A.: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5), 463–470 (1993)

    Article  MathSciNet  Google Scholar 

  41. Zelikovsky, A.: Better approximation bounds for the network and euclidean Steiner tree problems. In: Technical report CS-96-06. University of Virginia. Charlottesville, VA, USA (1996)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan, Taiwan, ROC

    Chi-Yeh Chen & Sun-Yuan Hsieh

Authors
  1. Chi-Yeh Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sun-Yuan Hsieh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sun-Yuan Hsieh .

Editor information

Editors and Affiliations

  1. The University of Texas at Dallas, Richardson, TX, USA

    Ding-Zhu Du

  2. University of Massachusetts Lowell, Lowell, MA, USA

    Jie Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Chen, CY., Hsieh, SY. (2020). An Efficient Approximation Algorithm for the Steiner Tree Problem. In: Du, DZ., Wang, J. (eds) Complexity and Approximation. Lecture Notes in Computer Science(), vol 12000. Springer, Cham. https://doi.org/10.1007/978-3-030-41672-0_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-41672-0_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-41671-3

  • Online ISBN: 978-3-030-41672-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation