nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

An Efficient Approximation Algorithm for the Steiner Tree Problem

verfasst von : Chi-Yeh Chen, Sun-Yuan Hsieh

Erschienen in: Complexity and Approximation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Note on the Position Value for Hypergraph Communication Situations

Nächstes Kapitel A Review for Submodular Optimization on Machine Scheduling Problems

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)MathSciNetCrossRef

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)MathSciNetCrossRef

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

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)MathSciNetCrossRef

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_8CrossRefMATH

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

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

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

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

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)

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_14CrossRef

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_12CrossRef

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 ComputingMathSciNetCrossRef

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)MathSciNetCrossRef

15.

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

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)MathSciNetCrossRef

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)MathSciNetCrossRef

18.

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

19.

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

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)

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)

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)MathSciNetCrossRef

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)

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)

25.

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

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_25CrossRef

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)MathSciNetCrossRef

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

29.

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

30.

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

31.

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

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)

33.

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

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)MathSciNetCrossRef

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)MathSciNetCrossRef

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)MathSciNetCrossRef

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/BFb0023489CrossRef

38.

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

39.

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

40.

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

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)

Titel: An Efficient Approximation Algorithm for the Steiner Tree Problem
verfasst von: Chi-Yeh Chen
Sun-Yuan Hsieh
Verlag: Springer International Publishing
Buch: Complexity and Approximation
Print ISBN: 978-3-030-41671-3

Electronic ISBN: 978-3-030-41672-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-41672-0_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"