[{"publication_identifier":{"isbn":["0898714346"]},"scopus_import":"1","language":[{"iso":"eng"}],"date_updated":"2023-02-17T12:08:26Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","author":[{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Leonardi   , Stefano","first_name":"Stefano","last_name":"Leonardi   "}],"oa_version":"None","year":"1999","day":"01","title":"Scheduling multicasts on unit-capacity trees and meshes","conference":{"location":"Baltimore, MD, United States","name":"SODA: Symposium on Discrete Algorithms","end_date":"1999-01-19","start_date":"1999-01-17"},"citation":{"apa":"Henzinger, M. H., &#38; Leonardi   , S. (1999). Scheduling multicasts on unit-capacity trees and meshes. In <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 438–447). Baltimore, MD, United States: Society for Industrial &#38; Applied Mathematics.","ama":"Henzinger MH, Leonardi    S. Scheduling multicasts on unit-capacity trees and meshes. In: <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial &#38; Applied Mathematics; 1999:438-447.","short":"M.H. Henzinger, S. Leonardi   , in:, 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial &#38; Applied Mathematics, 1999, pp. 438–447.","mla":"Henzinger, Monika H., and Stefano Leonardi   . “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial &#38; Applied Mathematics, 1999, pp. 438–47.","ista":"Henzinger MH, Leonardi    S. 1999. Scheduling multicasts on unit-capacity trees and meshes. 10th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 438–447.","ieee":"M. H. Henzinger and S. Leonardi   , “Scheduling multicasts on unit-capacity trees and meshes,” in <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Baltimore, MD, United States, 1999, pp. 438–447.","chicago":"Henzinger, Monika H, and Stefano Leonardi   . “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” In <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 438–47. Society for Industrial &#38; Applied Mathematics, 1999."},"status":"public","publication":"10th Annual ACM-SIAM Symposium on Discrete Algorithms","quality_controlled":"1","publisher":"Society for Industrial & Applied Mathematics","publication_status":"published","_id":"11925","date_created":"2022-08-18T12:45:50Z","abstract":[{"lang":"eng","text":"This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput-model. The problem is a generalization of the edge-disjoint paths problem and is NPhard both on trees and meshes. We study both the offline and the online version of the problem: In the offline setting, we give the first\r\nconstant-factor approximation algorithm for trees, and an O((log log n)*)-factor approximation algorithm for meshes, where n is the number of nodes in the graph. In the online setting, we give the first polylogarithrnic competitive online algorithm for tree and mesh topologies. No polylogarithmic-competitive algorithm is possible on general network topologies [8] and there\r\nexists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies [l]. We prove the same lower bound for meshes. "}],"date_published":"1999-01-01T00:00:00Z","month":"01","extern":"1","article_processing_charge":"No","page":"438-447"}]