{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:00:14Z","timestamp":1787385614917,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone model by a factor of $O(\\frac{\\log n}{\\log\\log k})$. No approximation algorithms were known for the general model considered in this paper.<\/jats:p>","DOI":"10.1137\/s0097539798347906","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"347-358","source":"Crossref","is-referenced-by-count":47,"title":["Message Multicasting in Heterogeneous Networks"],"prefix":"10.1137","volume":"30","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)90022-1"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"V. Bala, J. Bruck, R. Cypher, P. Elustondo, A. Ho, C. T. Ho, S. Kipnis, and M. Snir,\n                      CCL: A portable and tunable collective communication library for scalable parallel computers\n                      , in Proceedings of the Eighth International Parallel Processing Symposium, Cancun, Mexico, IEEE Press, Piscataway, NJ, 1994, pp. 835\u2013844.","DOI":"10.1109\/IPPS.1994.288208"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01184933"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Bar\u2010Noy, S. Kipnis, and B. Schieber,\n                      Optimal multiple message broadcasting in telephone\u2010like communication systems\n                      , in Proceedings of the Sixth Symposium on Parallel and Distributed Processing, Dallas, TX, IEEE Press, Piscataway, NJ, 1994, pp. 216\u2013223.","DOI":"10.1109\/SPDP.1994.346164"},{"key":"R5","unstructured":"E. Cockayne and A. Thomason,\n                      Optimal multi\u2010message broadcasting in complete graphs\n                      , in Proceedings of the Eleventh SE Conference on Combinatorics, Graph Theory, and Computing, 1980, pp. 181\u2013199."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. J. Dinneen, M. R. Fellows, and V. Faber,\n                      Algebraic construction of efficient networks\n                      , Applied Algebra, Algebraic Algorithms, and Error Correcting Codes (AAECC), Lecture Notes in Comput. Sci. 539, Springer, Berlin, 1991, pp. 152\u2013158.","DOI":"10.1007\/3-540-54522-0_104"},{"key":"R7","unstructured":"Express User\u2019s Guide, Version 3.0\n                      , Parasoft Corporation, Monrovia, CA, 1995."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0139032"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Uriel Feige, A threshold of lnn for approximating set cover (preliminary version), ACM, New York, 1996, 314\u20133181427527","DOI":"10.1145\/237814.237977"},{"key":"R10","unstructured":"G. Fox, M. Johnson, G. Lyzenga, S. Otto, J. Salmon, and D. Walker,\n                      Solving Problems on Concurrent Processors, Volume I : General Techniques and Regular Problems\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1988."},{"key":"R11","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP\u2010Completeness\n                      , W. H. Freeman, San Francisco, CA, 1979."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190606"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0404021"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180406"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840353"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193245923"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Karp, A. Sahay, E. Santos, and K. E. Schauser,\n                      Optimal broadcast and summation in the LogP model\n                      , in Proceedings of the Fifth Symposium on Parallel Algorithms and Architectures (SPAA), Association for Computing Machinery, New York, 1993.","DOI":"10.1145\/165231.165250"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0401049"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90066-I"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"R. Ravi,\n                      Rapid rumor ramification: Approximating the minimum broadcasting time\n                      , in Proceedings of the 35th Symposium on Foundations of Computer Science (FOCS), Santa Fe, NM, IEEE Press, Piscataway, NJ, 1994, pp. 202\u2013213.","DOI":"10.1109\/SFCS.1994.365693"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180205"},{"key":"R22","unstructured":"M. Snir, S. Otto, S. Huss\u2010Lederman, D. Walker, and J. Dongarra,\n                      MPI\u2014The Complete Reference, Vol. 1, The MPI\u20101 Core\n                      , 2nd ed., MIT Press, Cambridge, MA, 1998."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"A. Srinivasan and C.\u2010P. Teo,\n                      A constant\u2010factor approximation algorithm for packet routing, and balancing local vs. global criteria\n                      , in Proceedings of the 29th Symposium on Theory of Computing (STOC), Association for Computing Machinery, New York, 1997, pp. 636\u2013643.","DOI":"10.1145\/258533.258658"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230505"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90153-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539798347906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:48Z","timestamp":1787336508000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539798347906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539798347906"],"URL":"https:\/\/doi.org\/10.1137\/s0097539798347906","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}