Abstract
We consider natural generalizations of the minimum broadcast time problem under the telephone model, where a rumor from a root node must be sent via phone calls to the whole graph in the minimum number of rounds; the telephone model implies that the set of edges involved in communicating in a round form a matching. The extensions we consider involve generalizing the number of calls that a vertex may participate in (the capacitated version), allowing conference calls (the hyperedge version) as well as a new multicommodity version we introduce where the rumors are no longer from a single node but from different sources and intended for specific destinations (the multicommodity version). Based on the ideas from [6,7], we present a very simple greedy algorithm for the basic multicast problem with logarithmic performance guarantee and adapt it to the extensions to design typically polylogarithmic approximation algorithms. For the multi-commodity version, we give the first approximation algorithm with performance ratio \(2^{ O\left(\log\log k \sqrt{\log k}\right)}\) for k source-sink pairs. We provide nearly matching lower bounds for the hypercasting problem. For the multicommodity multicasting problem, we present improved guarantees for other variants involving asymmetric capacities, small number of terminals and with larger additive guarantees.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Awerbuch, B., Kutten, S., Peleg, D.: On buffer-economical store-and-forward deadlock prevention. IEEE Transactions on Communication 42, 2934–2937 (1994)
Baker, B., Shostak, R.: Gossips and telephones. Discrete Math 2, 191–193 (1972)
Censor-Hillel, K., Haeupler, B., Kelner, J., Maymounkov, P.: Global Computation in a Poorly Connected World: Fast Rumor Spreading No Dependence on Conductance. In: STOC: ACM Symposium on Theory of Computing (2012)
Dvork, T.: Chromatic Index of Hypergraphs and Shannons Theorem. European Journal of Combinatorics 21(5), 585–591 (2000)
Elkin, M., Kortsarz, M.G.: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. In: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC 2002 (2002)
Elkin, M., Kortsarz, G.: An approximation algorithm for the directed telephone multicast problem. Algorithmica 45(4), 569–583 (2006)
Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast. In: SODA 2003 Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 76–85 (2003)
Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. System Sci. 57, 187–199 (1998)
Grigni, M., Peleg, D.: Tight bounds on minimum broadcast networks. SIAM J. Discrete Math. 4, 207–222 (1991)
Guha, S., Bar-noy, A., Naor, J., Schieber, B.: Multicasting in heterogeneous networks. In: STOC 1998 Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 448–453 (1998)
Guruswami, V., Sinop, A.K.: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. In: SODA 2011 Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1615–1626 (2011)
Hajnal, A., Milner, E.C., Szemeredi, E.: A cure for the telephone disease. Canad Math. Bull 15, 447–450 (1976)
Haeupler, B.: Simple, Fast, and Deterministic Gossip and Rumor Spreading. In: SODA: ACM-SIAM Symposium on Discrete Algorithms (2013)
Kortsarz, G., Peleg, D.: Approximation algorithms for minimum time broadcast. SIAM Journal on Discrete Methods 8, 401–427 (1995)
Kossinets, G., Kleinberg, J., Watts, D.: The structure of information pathways in a social communication network. In: Proceedings of the 14th SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 435–443 (2008)
Leighton, F.T., Lewin, D.M.: Global Hosting System, US Patent 6108703 (Issued August 22, 2000)
Onus, M., Richa, A.W.: Minimum maximum-degree publish-subscribe overlay network design. IEEE/ACM Transactions on Networking, TON (2011)
Proskurowski, A.: Minimum broadcast trees. IEEE Trans. Comput. C-30, 363 (1981)
Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. In: 27th Annual Symposium on Foundations of Computer Science (FOCS 1986), pp. 10–18 (1986)
Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: 35th Annual Symposium on Foundations of Computer Science, FOCS 1994 (1994)
Scheuermann, P., Wu, G.: Heuristic Algorithms for Broadcasting in Point-to-Point Computer Networks. IEEE Transactions on Computers 33(9), 804–811 (1984)
Schrijver, A.: Combinatorial optimization: Polyhedra and Eficiency, ch. 21. Springer (2003)
Tijdeman, R.: On a Telephone Problem. Nieuw Arch. Wisk. 19, 188–192 (1971)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nikzad, A., Ravi, R. (2014). Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast Problems. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43951-7_48
Download citation
DOI: https://doi.org/10.1007/978-3-662-43951-7_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43950-0
Online ISBN: 978-3-662-43951-7
eBook Packages: Computer ScienceComputer Science (R0)