{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:22:13Z","timestamp":1766136133898},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_28","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"324-335","source":"Crossref","is-referenced-by-count":12,"title":["Better Scalable Algorithms for Broadcast Scheduling"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Ravishankar","family":"Krishnaswamy","sequence":"additional","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","first-page":"215","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"N. Bansal","year":"2005","unstructured":"Bansal, N., Charikar, M., Khanna, S., Naor, J.: Approximating the average response time in broadcast scheduling. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 215\u2013221. ACM, New York (2005) (electronic)"},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1145\/1109557.1109596","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Coppersmith, D., Sviridenko, M.: Improved approximation algorithms for broadcast scheduling. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 344\u2013353. ACM, New York (2006)"},{"key":"28_CR3","unstructured":"Bansal, N., Krishnaswamy, R., Nagarajan, V.: Better scalable algorithms for broadcast scheduling. Technical Report CMU-CS-09-174, Carnegie Mellon University, Pittsburgh (2009)"},{"key":"28_CR4","unstructured":"Bartal, Y., Muthukrishnan, S.: Minimizing maximum response time in scheduling broadcasts. In: SODA 2000: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 558\u2013559 (2000)"},{"key":"28_CR5","first-page":"473","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Chang","year":"2008","unstructured":"Chang, J., Erlebach, T., Gailis, R., Khuller, S.: Broadcast scheduling: algorithms and complexity. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 473\u2013482. ACM, New York (2008)"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1109557.1109594","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M. Charikar","year":"2006","unstructured":"Charikar, M., Khuller, S.: A robust maximum completion time measure for scheduling. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 324\u2013333. ACM, New York (2006)"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Im, S., Moseley, B.: Longest wait first and broadcast scheduling. In: WAOA 2009- Workshop on Approximation and Online Algorithms (2009)","DOI":"10.1007\/978-3-642-12450-1_6"},{"key":"28_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-642-04128-0_40","volume-title":"Algorithms - ESA 2009","author":"C. Chekuri","year":"2009","unstructured":"Chekuri, C., Im, S., Moseley, B.: Minimizing maximum response time and delay factor in broadcast scheduling. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 444\u2013455. Springer, Heidelberg (2009)"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Moseley, B.: Online scheduling to minimize the maximum delay factor. In: SODA 2009: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 1116\u20131125 (2009)","DOI":"10.1137\/1.9781611973068.121"},{"issue":"1","key":"28_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-3975(99)00186-3","volume":"235","author":"J. Edmonds","year":"2000","unstructured":"Edmonds, J.: Scheduling in the dark. Theoret. Comput. Sci.\u00a0235(1), 109\u2013141 (2000); Selected papers in honor of Manuel Blum, Hong Kong (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"28_CR11","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s00453-003-1018-5","volume":"36","author":"J. Edmonds","year":"2003","unstructured":"Edmonds, J., Pruhs, K.: Multicast pull scheduling: when fairness is fine. Algorithmica\u00a036(3), 315\u2013330 (2003) (Online algorithms)","journal-title":"Algorithmica"},{"issue":"1","key":"28_CR12","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1077464.1077467","volume":"1","author":"J. Edmonds","year":"2005","unstructured":"Edmonds, J., Pruhs, K.: A maiden analysis of longest wait first. ACM Trans. Algorithms\u00a01(1), 14\u201332 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. In: SODA 2009: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 685\u2013692 (2009)","DOI":"10.1137\/1.9781611973068.75"},{"issue":"3","key":"28_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1023\/B:JOSH.0000019682.75022.96","volume":"7","author":"T. Erlebach","year":"2004","unstructured":"Erlebach, T., Hall, A.: NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. J. Sched.\u00a07(3), 223\u2013241 (2004)","journal-title":"J. Sched."},{"issue":"4","key":"28_CR15","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10951-007-0036-6","volume":"11","author":"S.P.Y. Fung","year":"2008","unstructured":"Fung, S.P.Y., Zheng, F., Chan, W.-T., Chin, F.Y.L., Poon, C.K., Wong, P.W.H.: Improved on-line broadcast scheduling with deadlines. J. Sched.\u00a011(4), 299\u2013308 (2008)","journal-title":"J. Sched."},{"issue":"4","key":"28_CR16","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00453-003-1058-x","volume":"38","author":"R. Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Kim, Y.-A., Wan, Y.-C.: Algorithms for minimizing response time in broadcast scheduling. Algorithmica\u00a038(4), 597\u2013608 (2004)","journal-title":"Algorithmica"},{"issue":"3","key":"28_CR17","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R. Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM\u00a053(3), 324\u2013360 (2006) (electronic)","journal-title":"J. ACM"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: An online scalable algorithm for average flowtime in broadcast scheduling. In: SODA 2010: Twentyfirst Annual ACM-SIAM Symposium on Discrete Algorithms (2010)","DOI":"10.1137\/1.9781611973075.107"},{"issue":"4","key":"28_CR19","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM\u00a047(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"issue":"6","key":"28_CR20","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1002\/jos.87","volume":"4","author":"B. Kalyanasundaram","year":"2001","unstructured":"Kalyanasundaram, B., Pruhs, K.R., Velauthapillai, M.: Scheduling broadcasts in wireless networks. J. Sched.\u00a04(6), 339\u2013354 (2001)","journal-title":"J. Sched."},{"issue":"3","key":"28_CR21","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.tcs.2004.02.047","volume":"325","author":"J.-H. Kim","year":"2004","unstructured":"Kim, J.-H., Chwa, K.-Y.: Scheduling broadcasts with deadlines. Theoret. Comput. Sci.\u00a0325(3), 479\u2013488 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"28_CR22","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Online scheduling. In: Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004)"},{"key":"28_CR23","unstructured":"Robert, J., Schabanel, N.: Pull-based data broadcast with dependencies: be fair to users, not to items. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 238\u2013247 (2007)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:18Z","timestamp":1606186098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}