research-article

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

Authors:

Hans Jürgen Prömel,

Angelika StegerAuthors Info & Claims

Journal of Algorithms, Volume 36, Issue 1

Pages 89 - 101

https://doi.org/10.1006/jagm.2000.1086

Published: 01 July 2000 Publication History

Abstract

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5/3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5/3+ for all 0. This is achieved by considering a related problem, the minimum spanning tree problem in weighted 3-uniform hypergraphs. For that problem we give a fully polynomial randomized approximation scheme. Our approach also gives rise to conceptually much easier and faster (though randomized) sequential approximation algorithms for the Steiner tree problem than the currently best known algorithms from Karpinski and Zelikovsky which almost match their approximation factor.

References

[1]

S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, 1992.

[2]

P. Berman, V. Ramaiyer, Improved approximations for the Steiner tree problem, J. Algorithms, 17 (1994) 381-408.

Digital Library

[3]

M. Bern, P. Plassmann, The Steiner problem with edge lengths 1 and 2, Inform. Process. Lett., 32 (1989) 171-176.

[4]

A. Borchers, D.-Z. Du, The k-Steiner ratio in graphs, 1995.

[5]

P.M. Camerini, G. Galbiati, F. Maffioli, Random pseudo-polynomial algorithms for exact matroid problems, J. Algorithms, 13 (1992) 258-273.

Digital Library

[6]

Choukhmane El-Arbi, Une heuristique pour le problème de l'arbre de Steiner, RAIRO. Rech. Opér., 12 (1978) 207-212.

[7]

D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, 1987.

[8]

S.E. Dreyfus, R.A. Wagner, The Steiner problem in graphs, Networks, 1 (1972) 195-207.

[9]

D.-Z. Du, Y.-J. Zhang, Q. Feng, On better heuristic for Euclidean Steiner minimum trees, 1991.

[10]

H.N. Gabow, M. Stallmann, An augmenting path algorithm for linear matroid parity, Combinatorics, 6 (1986) 123-150.

Digital Library

[11]

R. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, Plenum, New York, 1972, pp. 85-103.

[12]

M. Karpinski, A.Z. Zelikovsky, New approximation algorithms for the Steiner tree problem, J. Comb. Optim., 1 (1997) 47-65.

[13]

L. Kou, G. Markowsky, L. Berman, A fast algorithm for Steiner trees, Acta Inform., 15 (1981) 141-145.

Digital Library

[14]

S. Lang, Addison¿Wesley, Reading, 1993.

[15]

L. Lovász, The matroid matching problem, Colloquia Mathematica Societatis János Bolyai, Szeged, 1978.

[16]

L. Lovász, On determinants, matchings and random algorithms, Fund. Comput. Theory, 79 (1979) 565-574.

[17]

K. Mulmuley, U. Vazirani, V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, 7 (1987) 105-113.

Digital Library

[18]

H. Narayanan, H. Saran, V.V. Vazirani, Randomized parallel algorithms for matroid union and intersection, with applications to arboreseces and edge-disjoint spanning trees, SIAM J. Comput., 23 (1994) 387-397.

Digital Library

[19]

V. Pan, Fast and efficient algorithms for the exact inversion of integer matrices, Springer-Verlag, Berlin/New York, 1985.

[20]

H.J. Prömel, A. Steger, Vieweg Verlag, Wiesbaden, 2000.

[21]

H. Takahashi, A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japon., 24 (1980) 573-577.

[22]

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

[23]

A. Z. Zelikovsky, Better Approximation Algorithms for the Network and Euclidean Steiner Tree Problems, Technical report, Kishinev, 1995.

Cited By

Yang BZheng W(2024)A Powerful Local Search Method for Minimum Steiner Tree ProblemWeb and Big Data10.1007/978-981-97-7241-4_4(50-66)Online publication date: 31-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7241-4_4
Zhang JLiu ZDeng XYin JWilliams BChen YNeville J(2023)Truthful mechanisms for steiner tree problemsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25729(5884-5891)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25729
Yang BZheng W(2023)Near-optimal Steiner tree computation powered by node embeddingsKnowledge and Information Systems10.1007/s10115-023-01893-865:11(4563-4583)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s10115-023-01893-8
Show More Cited By

Index Terms

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Hypergraphs
      2. Trees
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

An approximation algorithm for the group Steiner problem
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

The input in the Group-Steiner Problem consists of an undirected connected graph with a cost function p(e) over the edges and a collection of subsets of vertices {g_i}. Each subset g_i is called a group and the vertices in ∪ g_i are called terminals. The ...
A greedy approximation algorithm for the group Steiner problem

In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices {g"i}"i"="1^m. Each subset g"i is called a group and the vertices in @?"ig"i are called terminals. It is required to find a minimum weight tree that ...
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

Given a weighted graph with some subsets of vertices called groups, the group Steiner tree problem is to find a minimum-weight subgraph which contains at least one vertex from each group. We give a randomized algorithm with a polylogarithmic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Algorithms

Journal of Algorithms Volume 36, Issue 1

July 2000

117 pages

ISSN:0196-6774

Editors:
Zvi Galil
Columbia Univ., New York, NY
,
David S. Johnson
AT&T Lab, Florham Park, NJ
,
Donald E. Knuth
Stanford Univ., Stanford, CA

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 July 2000

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang BZheng W(2024)A Powerful Local Search Method for Minimum Steiner Tree ProblemWeb and Big Data10.1007/978-981-97-7241-4_4(50-66)Online publication date: 31-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7241-4_4
Zhang JLiu ZDeng XYin JWilliams BChen YNeville J(2023)Truthful mechanisms for steiner tree problemsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25729(5884-5891)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25729
Yang BZheng W(2023)Near-optimal Steiner tree computation powered by node embeddingsKnowledge and Information Systems10.1007/s10115-023-01893-865:11(4563-4583)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s10115-023-01893-8
Lokshtanov DMisra PPanolan FSaurabh SZehavi M(2023)An ETH-Tight Algorithm for Bidirected Steiner ConnectivityAlgorithms and Data Structures10.1007/978-3-031-38906-1_39(588-604)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-38906-1_39
Bhore SCarmi PKolay SZehavi M(2022)Parameterized Study of Steiner Tree on Unit Disk GraphsAlgorithmica10.1007/s00453-022-01020-z85:1(133-152)Online publication date: 5-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-01020-z
Călinescu GWang X(2022)Combination Algorithms for Steiner Tree VariantsAlgorithmica10.1007/s00453-022-01009-885:1(153-169)Online publication date: 8-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-01009-8
Chitnis RFeldmann AManurangsi P(2021)Parameterized Approximation Algorithms for Bidirected Steiner Network ProblemsACM Transactions on Algorithms10.1145/344758417:2(1-68)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3447584
Saikia PKarmakar S(2021)Improved distributed approximation for Steiner tree in the CONGEST modelJournal of Parallel and Distributed Computing10.1016/j.jpdc.2021.08.004158:C(196-212)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.jpdc.2021.08.004
Saikia PKarmakar S(2020)Round-Message Trade-Off in Distributed Steiner Tree Construction in the CONGEST ModelDistributed Computing and Internet Technology10.1007/978-3-030-36987-3_7(111-126)Online publication date: 9-Jan-2020
https://dl.acm.org/doi/10.1007/978-3-030-36987-3_7
Bateni MFarhadi AHajiaghayi MChan T(2019)Polynomial-time approximation scheme for minimum k-cut in planar and minor-free graphsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310500(1055-1068)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310500
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents