research-article

A simple 2(1-1/l) factor distributed approximation algorithm for steiner tree in the CONGEST model

Authors:

Parikshit Saikia,

Sushanta KarmakarAuthors Info & Claims

ICDCN '19: Proceedings of the 20th International Conference on Distributed Computing and Networking

Pages 41 - 50

https://doi.org/10.1145/3288599.3288629

Published: 04 January 2019 Publication History

Abstract

The Steiner tree problem is a classical and fundamental problem in combinatorial optimization. The best known deterministic distributed algorithm for the Steiner tree problem in the CONGEST model was proposed by Lenzen and Patt-Shamir [25] that constructs a Steiner tree whose cost is optimal upto a factor of 2 and the round complexity is [MATH HERE] for a graph of n nodes and t terminals, where S is the shortest path diameter of the graph. Note here that the Õ (·) notation hides polylogarithmic factors in n. In this paper we present a simple deterministic distributed algorithm for constructing a Steiner tree in the CONGEST model with an approximation factor [MATH HERE] of the optimal where ℓ is the number of terminal leaf nodes in the optimal Steiner tree. The round complexity of our algorithm is [MATH HERE] and the message complexity is O(Δ(n − t)S + n^3/2, where Δ is the maximum degree of a vertex in the graph. Our algorithm is based on the computation of a sub-graph called the shortest path forest for which we present a separate deterministic distributed algorithm with round and message complexities of O(S) and O(Δ(n - t)S) respectively.

References

[1]

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

[2]

Baruch Awerbuch, Oded Goldreich, Ronen Vainish, and David Peleg. 1990. A Trade-off Between Information and Communication in Broadcast Protocols. Journal of the ACM (JACM) 37, 2 (1990), 238--256.

Digital Library

[3]

Leonid Barenboim, Michael Elkin, and Fabian Kuhn. 2014. Distributed (Δ + 1)-Coloring in Linear (in Δ) Time. SIAM J. Comput. 43, 1 (2014), 72--95.

Digital Library

[4]

Fred Bauer and Anujan Varma. 1996. Distributed Algorithms for Multicast Path Setup in Data Networks. IEEE/ACM Transaction Networks 4, 2 (1996), 181--191.

Digital Library

[5]

Richard Bellman. 1958. ON A ROUTING PROBLEM. Quart. Appl. Math. 16, 1 (1958), 87--90.

[6]

Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanita. 2010. An Improved LP-based Approximation for Steiner Tree. In Proceedings of the Forty-second ACM Symposium on Theory of Computing (STOC '10). 583--592.

Digital Library

[7]

Parinya Chalermsook and Jittat Fakckeroenphol. 2005. Simple distributed algorithm for approximating minimum Steiner tree. In The 11st International Computing and Combinatorics Conference (COCOON '05). 380--389.

[8]

Miroslav Chlebík and Janka Chlebíková. 2008. The Steiner Tree Problem on Graphs: Inapproximability Results. Theoretical Computer Science 406, 3 (2008), 207--214.

Digital Library

[9]

Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2011. Distributed Verification and Hardness of Distributed Approximation. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC '11). 363--372.

Digital Library

[10]

Michael Elkin. 2017. Distributed Exact Shortest Paths in Sublinear Time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC '17). 757--770.

Digital Library

[11]

Lester Jr. Ford. 1956. Network Flow Theory. Santa Monica, California, RAND Corporation (1956).

[12]

Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. 2012. Networks Cannot Compute Their Diameter in Sublinear Time. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12). 1150--1162.

Digital Library

[13]

Juan A. Garay, Shay Kutten, and David Peleg. 1998. A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees. SIAM J. Comput. 27, 1 (Feb. 1998), 302--316.

Digital Library

[14]

Luca Gatani, Giuseppe Lo Re, and Salvatore Gaglio. 2006. An efficient distributed algorithm for generating and updating multicast trees. Parallel Comput. 32, 11 (2006), 777 -- 793.

Digital Library

[15]

Chen Gen-Huey, Michael E. Houle, and Kuo Ming-Ter. 1993. The Steiner problem in distributed computing systems. Information Sciences 74, 1 (1993), 73 -- 96.

Digital Library

[16]

Mohsen Ghaffari. 2016. An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16). 270--277.

Digital Library

[17]

M. Hauptmann and M. Karpinski. Retrived April 2015. A Compendium on Steiner Tree Problems. http://theory.cs.unibonn.de/info5/steinerkompendium/netcompendium.html (Retrived April 2015).

[18]

Stephan Holzer and Roger Wattenhofer. 2012. Optimal Distributed All Pairs Shortest Paths and Applications. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC '12). 355--364.

Digital Library

[19]

Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Proceedings of a Symposium on the Complexity of Computer Computations. 85--103.

[20]

Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar. 2008. Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings. Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, 263--272.

Digital Library

[21]

Liah Kor, Amos Korman, and David Peleg. 2013. Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification. Theory of Computing Systems 53, 2 (2013), 318--340.

[22]

L. Kou, G. Markowsky, and L. Berman. 1981. A Fast Algorithm for Steiner Trees. Acta Informatica 15, 2 (1981), 141--145.

Digital Library

[23]

Fabian Kuhn and Rogert Wattenhofer. 2006. On the Complexity of Distributed Graph Coloring. In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing (PODC '06). 7--15.

Digital Library

[24]

Shay Kutten and David Peleg. 1998. Fast Distributed Construction of Small k-Dominating Sets and Applications. Journal of Algorithms 28, 1 (1998), 40 -- 66.

Digital Library

[25]

Christoph Lenzen and Boaz Patt-Shamir. 2014. Improved Distributed Steiner Forest Construction. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC '14). 262--271.

Digital Library

[26]

Karpinski Marek and Zelikovsky Alexander. 1997. New Approximation Algorithms for the Steiner Tree Problems. Journal of Combinatorial Optimization 1, 1 (1997), 47--65.

[27]

Roman Novak, Joze Rugelj, and Gorazd Kandus. 2001. A note on distributed multicast routing in point-to-point networks. Computers and Operation Research 28, 12 (2001), 1149--1164.

Digital Library

[28]

David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM : Discrete Mathematics and Applications (2000).

Digital Library

[29]

David Peleg and Vitaly Rubinovich. 2000. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM J. Comput. 30, 5 (2000), 1427--1442.

Digital Library

[30]

Hans Jurgen Promel and Angelika Steger. 2000. A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3. Journal of Algorithms 36, 1 (2000), 89 -- 101.

Digital Library

[31]

Gabriel Robins and Alexander Zelikovsky. 2000. Improved Steiner Tree Approximation in Graphs. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00). 770--779.

Digital Library

[32]

J. Rugelj and S. Klavzar. 1997. Distributed multicast routing in point-to-point networks. Computers and Operation Research 24 (1997), 521--527.

Digital Library

[33]

Johannes Schneider and Roger Wattenhofer. 2010. An optimal maximal independent set algorithm for bounded-independence graphs. Distributed Computing 22, 5 (2010), 349--361.

Digital Library

[34]

Gurdip Singh and Kusuma Vellanki. 1998. A Distributed Protocol for Constructing Multicast Trees. In In: 2nd International Conference On Principles Of Distributed Systems (OPODIS '98). 61--76.

[35]

H. Takahashi and A. Matasuyama. 1980. An approximate solution for the Steiner problem in graphs. Mathematics, Japan 24 (1980), 573--577.

[36]

Pawel Winter and J. Smith MacGregor. 1992. Path-distance heuristics for the Steiner problem in undirected networks. Algorithmica 7, 1 (1992), 309--327.

Digital Library

[37]

Y. F. Wu, P. Widmayer, and C. K. Wong. 1986. A faster approximation algorithm for the Steiner problem in graphs. Acta Informatica 23, 2 (1986), 223--229.

Digital Library

Cited By

Saikia PKarmakar S(2019)2(1 – 1/ℓ)-Factor Steiner Tree Approximation in Õ(n^1/3) Rounds in the CONGESTED CLIQUE2019 Seventh International Symposium on Computing and Networking (CANDAR)10.1109/CANDAR.2019.00018(82-91)Online publication date: Nov-2019
https://doi.org/10.1109/CANDAR.2019.00018

Index Terms

A simple 2(1-1/l) factor distributed approximation algorithm for steiner tree in the CONGEST model
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Improved distributed steiner forest construction
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant ε>0, a (2+ε)-approximation in ~O(sk+√{min(st,n)}) rounds, where s is the shortest path diameter, t is ...
Improved distributed approximation for Steiner tree in the CONGEST model
Highlights
- Improved distributed approximation for Steiner tree.
- Approximation algorithms ...
Abstract
In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 ( 1 − 1 / ℓ )-approximate ST using O ( S + n log ⁎ ⁡ n ) rounds and O ( m S + n ...
Round-Message Trade-Off in Distributed Steiner Tree Construction in the CONGEST Model
Distributed Computing and Internet Technology
Abstract
The Steiner tree problem is one of the fundamental optimization problems in distributed graph algorithms. Recently Saikia and Karmakar [27] proposed a deterministic distributed algorithm for the Steiner tree problem that constructs a Steiner tree ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICDCN '19: Proceedings of the 20th International Conference on Distributed Computing and Networking

January 2019

535 pages

ISBN:9781450360944

DOI:10.1145/3288599

General Chairs:
R. C. Hansdah
IISc Bangalore, India Paolo Bellavista, University of Bologna, Italy
,
Dilip Krishnaswamy
Reliance Jio Infocomm, India Sriram V. Pemmaraju, University of Iowa
,
Nitin Vaidya
Georgetown University

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
Indian Institute of Science: Indian Institute of Science

In-Cooperation

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 January 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICDCN '19

Sponsor:

SIGOPS
Indian Institute of Science

ICDCN '19: International Conference on Distributed Computing and Networking

January 4 - 7, 2019

Bangalore, India

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
146
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saikia PKarmakar S(2019)2(1 – 1/ℓ)-Factor Steiner Tree Approximation in Õ(n^1/3) Rounds in the CONGESTED CLIQUE2019 Seventh International Symposium on Computing and Networking (CANDAR)10.1109/CANDAR.2019.00018(82-91)Online publication date: Nov-2019
https://doi.org/10.1109/CANDAR.2019.00018

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents