{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:42Z","timestamp":1750308822138,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>Many network applications that need to distribute content and data to a large number of clients use a hybrid scheme in which one (or more) multicast channel is used in parallel to a unicast dissemination. This way the application can distribute data using one of its available multicast channels or by sending one or more unicast transmissions. In such a model the utilization of the multicast channels is critical for the overall performance of the system.<\/jats:p>\n          <jats:p>\n            We study the scheduling algorithm of the sender in such a model. We describe this scheduling problem as an optimization problem where the objective is to maximize the utilization of the multicast channel. Our model captures the fact that it may be beneficial to multicast an object more than once (e.g., page update). Thus, the benefit depends, among other things, on the last time the object was sent, which makes the problem much more complex than previous related scheduling problems. We show that our problem is NP-hard. Then, using the\n            <jats:italic>local ratio technique<\/jats:italic>\n            we obtain a 4-approximation algorithm for the case where the objects are of fixed size and a 10-approximation algorithm for the general case. We also consider a special case which may be of practical interest, and prove that a simple greedy algorithm is a 3-approximation algorithm in this case.\n          <\/jats:p>","DOI":"10.1145\/1644015.1644029","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T13:16:40Z","timestamp":1282655800000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Time-dependent multi-scheduling of multicast"],"prefix":"10.1145","volume":"6","author":[{"given":"Rami","family":"Cohen","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Raz","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,12,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/288235.288248"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.811450"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_4_1","first-page":"27","article-title":"A local-ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"Bar-Yehuda R.","year":"1985","journal-title":"Annals Discr. Math."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Cohen R. 2004. Time dependent multi scheduling of multicast. M.S. thesis Technion-Israel Institute of Technology.  Cohen R. 2004. Time dependent multi scheduling of multicast. M.S. thesis Technion-Israel Institute of Technology.","DOI":"10.1007\/978-3-540-30140-0_21"},{"volume":"2","volume-title":"Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Society.","author":"Cohen R.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Fielding R. Gettys J. Mogul J. Frystyk H. Masinter L. Leach P. and Berners-Lee T. 1999. RFC 2616: Hypertext transfer protocol--HTTP\/1.1. http\/\/tools.ietf.org\/html\/rfc2186.   Fielding R. Gettys J. Mogul J. Frystyk H. Masinter L. Leach P. and Berners-Lee T. 1999. RFC 2616: Hypertext transfer protocol--HTTP\/1.1. http\/\/tools.ietf.org\/html\/rfc2186.","DOI":"10.17487\/rfc2616"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.650139"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/262116.262136"},{"volume-title":"Proceedings of the 37th IEEE Symposium on Foundations of Computer Science. 627--636","year":"1996","author":"H\u00e5stad J.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/505202.505224"},{"key":"e_1_2_1_13_1","volume-title":"Computer Networking: A Top-Down Approach Featuring the Internet","author":"Kurose J. F.","year":"2003","edition":"2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.564138"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Schulzrinne H. Rao A. and Lanphier R. 1998. RFC 2326: Real time streaming protocol (RTSP). http:\/\/www.ietf.org\/rfc\/rfc2326.txt   Schulzrinne H. Rao A. and Lanphier R. 1998. RFC 2326: Real time streaming protocol (RTSP). http:\/\/www.ietf.org\/rfc\/rfc2326.txt","DOI":"10.17487\/rfc2326"},{"volume-title":"Proceedings of the 16th Annual IEEE Conference on Computer Communications. 109--117","author":"Su C.-J.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Wessels D. and Claffy K. 1997. RFC 2186: Internet Cache Protocol (ICP) version 2. http:\/\/www.faqs.org\/rfcs\/rfc2186.html   Wessels D. and Claffy K. 1997. RFC 2186: Internet Cache Protocol (ICP) version 2. http:\/\/www.faqs.org\/rfcs\/rfc2186.html","DOI":"10.17487\/rfc2186"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644029","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1644015.1644029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:44Z","timestamp":1750278404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1644015.1644029"],"URL":"https:\/\/doi.org\/10.1145\/1644015.1644029","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2006-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}