{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:53:57Z","timestamp":1725576837892},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642183171"},{"type":"electronic","value":"9783642183188"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-18318-8_7","type":"book-chapter","created":{"date-parts":[[2011,1,24]],"date-time":"2011-01-24T03:58:06Z","timestamp":1295841486000},"page":"71-82","source":"Crossref","is-referenced-by-count":5,"title":["New Models and Algorithms for Throughput Maximization in Broadcast Scheduling"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avigdor","family":"Gal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sungjin","family":"Im","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"McCutchen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louiqa","family":"Raschid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Coppersmith, D., Sviridenko, M.: Improved approximation algorithms for broadcast scheduling. In: SODA, pp. 344\u2013353 (2006)","DOI":"10.1145\/1109557.1109596"},{"key":"7_CR2","unstructured":"Bartal, Y., Muthukrishnan, S.: Minimizing maximum response time inscheduling broadcasts. In: SODA, pp. 558\u2013559 (2000)"},{"key":"7_CR3","unstructured":"Calinescu, G., Chekuri, C., Pal, M., Vondrak, J.: Maximizing a monotone submodular set function subject to a matroid constraint. SIAM J. on Computing (to appear)"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-540-27798-9_24","volume-title":"Computing and Combinatorics","author":"W. Chan","year":"2004","unstructured":"Chan, W., Lam, T., Ting, H., Wong, P.: New Results on On-Demand Broadcasting with Deadline via Job Scheduling with Cancellation. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol.\u00a03106, pp. 210\u2013218. Springer, Heidelberg (2004)"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Carney, D., Lee, S., Zdonik, S.: Scalable Application-Aware Data Freshening. In: ICDE, pp. 481\u2013492 (2003)","DOI":"10.1109\/ICDE.2003.1260815"},{"key":"7_CR6","unstructured":"Chang, J., Erlebach, T., Gailis, R., Khuller, S.: Broadcast Scheduling: Algorithms and Complexity. In: SODA, pp. 473\u2013482 (2008)"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Khuller, S.: A robust maximum completion time measure for scheduling. In: SODA, pp. 324\u2013333 (2006)","DOI":"10.1145\/1109557.1109594"},{"key":"7_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":"7_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondrak, J., Zenklusen, R.: Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In: FOCS (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"1","key":"7_CR10","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10951-006-5595-4","volume":"9","author":"M. Chrobak","year":"2006","unstructured":"Chrobak, M., D\u00fcrr, C., Jawor, W., Kowalik, L., Kurowski, M.: A Note on Scheduling Equal-Length Jobs to Maximize Throughput. J. of Scheduling\u00a09(1), 71\u201373 (2006)","journal-title":"J. of Scheduling"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Deolasee, P., Katkar, A., Panchbudhe, P., Ramamritham, K., Shenoy, P.: Adaptive Push-Pull: Deisseminating Dynamic Web Data. In: WWW (2001)","DOI":"10.1145\/371920.372066"},{"issue":"1","key":"7_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1287\/ijoc.1060.0207","volume":"20","author":"J. Eckstein","year":"2007","unstructured":"Eckstein, J., Gal, A., Reiner, S.: Monitoring an Information Source under a Politeness Constraint. INFORMS Journal on Computing\u00a020(1), 3\u201320 (2007)","journal-title":"INFORMS Journal on Computing"},{"key":"7_CR13","unstructured":"Edmonds, J., Pruhs, K.: Multicast pull scheduling: when fairness is fine. In: SODA, pp. 421\u2013430 (2002)"},{"key":"7_CR14","unstructured":"Edmonds, J., Pruhs, K.: A maiden analysis of longest wait first. In: SODA, pp. 811\u2013820 (2004)"},{"issue":"6","key":"7_CR15","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1145\/504794.504797","volume":"48","author":"A. Gal","year":"2001","unstructured":"Gal, A., Eckstein, J.: Managing Periodically Updated Data in Relational Databases: A Stochastic Modeling Approach. JACM\u00a048(6), 1141\u20131183 (2001)","journal-title":"JACM"},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/3-540-47867-1_30","volume-title":"Integer Programming and Combinatorial Optimization","author":"R. Gandhi","year":"2002","unstructured":"Gandhi, R., Khuller, S., Kim, Y., Wan, Y.C.: Algorithms for minimizing response time in broadcast scheduling. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 415\u2013424. Springer, Heidelberg (2002)"},{"issue":"3","key":"7_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. JACM\u00a053(3), 324\u2013360 (2006); Preliminary version in FOCS (2002)","journal-title":"JACM"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling. In: SODA (2010)","DOI":"10.1137\/1.9781611973075.107"},{"issue":"4","key":"7_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"},{"key":"7_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-45253-2_27","volume-title":"Algorithms - ESA 2000","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K., Velauthapillai, M.: Scheduling broadcasts in wireless networks. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 290\u2013301. Springer, Heidelberg (2000)"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.tcs.2004.02.047","volume":"325","author":"J. Kim","year":"2004","unstructured":"Kim, J., Chwa, K.: Scheduling broadcasts with deadlines. Theor. Comput. Sci.\u00a0325, 479\u2013488 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"7_CR22","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/234313.234327","volume":"28","author":"R. Motwani","year":"1996","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. ACM Comput. Surveys\u00a028(1), 33\u201337 (1996)","journal-title":"ACM Comput. Surveys"},{"key":"7_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"1","key":"7_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming\u00a014(1), 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Pandey, S., Dhamdhere, K., Olston, C.: WIC: A General-Purpose Algorithm for Monitoring Web Information Sources. In: VLDB, pp. 360\u2013371 (2004)","DOI":"10.1016\/B978-012088469-8\/50034-6"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Roitman, H., Gal, A., Raschid, L.: Satisfying Complex Data Needs using Pull-Based Online Monitoring of Volatile Data Sources. In: ICDE (2008)","DOI":"10.1109\/ICDE.2008.4497591"},{"key":"7_CR27","unstructured":"Roitman, H.: Profile Based Online Data Delivery - Model and Algorithms. Ph.D. Thesis (2008)"},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Roitman, H., Gal, A., Raschid, L.: On Trade-offs in Event Delivery Systems. In: The 4th ACM International Conference on Distributed Event-Based Systems, DEBS (2010)","DOI":"10.1145\/1827418.1827449"},{"key":"7_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/11809678_34","volume-title":"Computing and Combinatorics","author":"F. Zheng","year":"2006","unstructured":"Zheng, F., Fung, S., Chan, W., Chin, F., Poon, C., Wong, P.: Improved On-Line Broadcast Scheduling with Deadlines. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 320\u2013329. Springer, Heidelberg (2006)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18318-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T22:56:38Z","timestamp":1559948198000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18318-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642183171","9783642183188"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18318-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}