{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:34Z","timestamp":1750306714586,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>\n            In the classical\n            <jats:italic>broadcast scheduling problem<\/jats:italic>\n            , there are\n            <jats:italic>n<\/jats:italic>\n            pages stored at a server, and requests for these pages arrive over time. Whenever a page is broadcast, it satisfies all outstanding requests for that page. The objective is to minimize average\n            <jats:italic>flow time<\/jats:italic>\n            of the requests. For any \u03f5 &gt; 0, we give a (1+\u03f5)-speed\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03f5\n            <jats:sup>3<\/jats:sup>\n            )-competitive online algorithm for broadcast scheduling. This improves over the recent breakthrough result of Im and Moseley [2010], where they obtained a (1+\u03f5)-speed\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03f5\n            <jats:sup>11<\/jats:sup>\n            )-competitive algorithm. Our algorithm and analysis are considerably simpler than Im and Moseley [2010]. More importantly, our techniques also extend to the general setting of\n            <jats:italic>nonuniform page sizes<\/jats:italic>\n            and\n            <jats:italic>dependent requests<\/jats:italic>\n            . This is the first scalable algorithm for broadcast scheduling with varying size pages and resolves the main open question from Im and Moseley [2010].\n          <\/jats:p>","DOI":"10.1145\/2636916","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Better Scalable Algorithms for Broadcast Scheduling"],"prefix":"10.1145","volume":"11","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravishankar","family":"Krishnaswamy","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Spencer","author":"Alon Noga","year":"2000","unstructured":"Noga Alon and Joel H . Spencer . 2000 . The Probabilistic Method (2nd ed.). Wiley , New York. Noga Alon and Joel H. Spencer. 2000. The Probabilistic Method (2nd ed.). Wiley, New York."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Bansal Nikhil","year":"2005","unstructured":"Nikhil Bansal , Moses Charikar , Sanjeev Khanna , and Joseph Naor . 2005 . Approximating the average response time in broadcast scheduling . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905) . 215--221. Nikhil Bansal, Moses Charikar, Sanjeev Khanna, and Joseph Naor. 2005. Approximating the average response time in broadcast scheduling. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). 215--221."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/060674417"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Bartal Yair","key":"e_1_2_1_4_1","unstructured":"Yair Bartal and S. Muthukrishnan . 2000. Minimizing maximum response time in scheduling broadcasts . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . 558--559. Yair Bartal and S. Muthukrishnan. 2000. Minimizing maximum response time in scheduling broadcasts. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). 558--559."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000815"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109594"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12450-1_6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_40"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496891"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00186-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133045"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1018-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077467"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496845"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOSH.0000019682.75022.96"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-007-0036-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1058-x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810482"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873708"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/647910.740477"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.047"},{"key":"e_1_2_1_24_1","unstructured":"K. Pruhs J. Sgall and E. Torng. 2004. Online scheduling. In Handbook of Scheduling: Algorithms Models and Performance Analysis Joseph Y.-T. Leung (Ed.). CRC Press.  K. Pruhs J. Sgall and E. Torng. 2004. Online scheduling. In Handbook of Scheduling: Algorithms Models and Performance Analysis Joseph Y.-T. Leung (Ed.). CRC Press."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Robert Julien","year":"2007","unstructured":"Julien Robert and Nicolas Schabanel . 2007 . Pull-based data broadcast with dependencies: Be fair to users, not to items . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . 238--247. Julien Robert and Nicolas Schabanel. 2007. Pull-based data broadcast with dependencies: Be fair to users, not to items. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 238--247."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636916","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2636916","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:22Z","timestamp":1750231162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2636916"],"URL":"https:\/\/doi.org\/10.1145\/2636916","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}