Multicommodity Multicast, Wireless and Fast

Authors R. Ravi, Oleksandr Rudenko



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.78.pdf
  • Filesize: 3.15 MB
  • 20 pages

Document Identifiers

Author Details

R. Ravi
  • Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, USA
Oleksandr Rudenko
  • Carnegie Mellon University, Pittsburgh, PA, USA

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. 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. Google Scholar
  3. Arthur M. Farley. Broadcast Time in Communication Networks. SIAM J. Appl. Math., pages 385-390, 1980. URL: https://doi.org/10.1137/0139032.
  4. András Hajnal, Eric C Milner, and Endre Szemerédi. A cure for the telephone disease. Canadian Mathematical Bulletin, 15(3):447-450, 1972. Google Scholar
  5. 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.
  6. 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. Google Scholar
  7. 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. Google Scholar
  8. 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. Google Scholar
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. 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. Google Scholar
  12. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail