LIPIcs.ESA.2019.78.pdf
- Filesize: 3.15 MB
- 20 pages
Document
Multicommodity Multicast, Wireless and Fast
Authors
-
Part of:
Volume:
27th Annual European Symposium on Algorithms (ESA 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-06
Cite As Get BibTex
R. Ravi and Oleksandr Rudenko. Multicommodity Multicast, Wireless and Fast. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.78
Abstract
We study rumor spreading in graphs, specifically multicommodity multicast problem under the wireless model: given source-destination pairs in the graph, one needs to find the fastest schedule to transfer information from each source to the corresponding destination. Under the wireless model, nodes can transmit to any subset of their neighbors in synchronous time steps, as long as they either transmit or receive from at most one transmitter during the same time step. We improve approximation ratio for this problem from O~(n^(2/3)) to O~(n^((1/2) + epsilon)) on n-node graphs. We also design an algorithm that satisfies p given demand pairs in O(OPT + p) steps, where OPT is the length of an optimal schedule, by reducing it to the well-studied packet routing problem. In the case where underlying graph is an n-node tree, we improve the previously best-known approximation ratio of O((log n)/(log log n)) to 3. One consequence of our proof is a simple constructive rule for optimal broadcasting in a tree under a widely studied telephone model.
Subject Classification
ACM Subject Classification
- Networks → Routing protocols
- Networks
Keywords
- Rumor
- scheduling
- broadcast
- multicommodity
- multicast
- optimization algorithms
- approximation
- packet routing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Marek Chrobak, Leszek Gaasieniec, and Wojciech Rytter. Fast broadcasting and gossiping in radio networks. Journal of Algorithms, pages 177-189, 2002. URL: https://doi.org/10.1016/S0196-6774(02)00004-4.
-
Michael Elkin and Guy Kortsarz. Sublogarithmic Approximation for Telephone Multiast. SODA Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 76-85, 2003.
- Arthur M. Farley. Broadcast Time in Communication Networks. SIAM J. Appl. Math., pages 385-390, 1980. URL: https://doi.org/10.1137/0139032.
-
András Hajnal, Eric C Milner, and Endre Szemerédi. A cure for the telephone disease. Canadian Mathematical Bulletin, 15(3):447-450, 1972.
- Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Arthur L. Liestman. A survey of gossiping and broadcasting in communication networks. Networks, pages 319-349, 1988. URL: https://doi.org/10.1002/net.3230180406.
-
Jennifer Iglesias, Rajmohan Rajaraman, R Ravi, and Ravi Sundaram. Rumors across radio, wireless, telephone. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
-
Jennifer Iglesias, Rajmohan Rajaraman, R Ravi, and Ravi Sundaram. Plane gossip: Approximating rumor spread in planar graphs. In Latin American Symposium on Theoretical Informatics, pages 611-624. Springer, 2018.
-
Tom Leighton, Bruce Maggs, and Satish Rao. Universal packet routing algorithms. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 256-269. IEEE, 1988.
-
Afshin Nikzad and R Ravi. Sending secrets swiftly: Approximation algorithms for generalized multicast problems. In International Colloquium on Automata, Languages, and Programming, pages 568-607. Springer, 2014.
-
R Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 202-213. IEEE, 1994.
-
Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis II. System level concurrency control for distributed database systems. ACM Transactions on Database Systems (TODS), pages 178-198, 1978.
- Aravind Srinivasan and Chung-Piaw Teo. A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. In STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 636-643, 1997. URL: https://doi.org/10.1145/258533.258658.