Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor

by Chandra Chekuri, Sungjin Im, and Benjamin Moseley

Theory of Computing, Volume 8(7), pp. 165-195, 2012

Bibliography with links to cited articles

[1]   Swarup Acharya, Michael Franklin, and Stanley Zdonik: Dissemination-based data delivery using broadcast disks. IEEE Personal Communications, 2(6):50–60, Dec 1995. [doi:10.1109/98.475988]

[2]   Demet Aksoy and Michael Franklin: R x W: A scheduling approach for large-scale on-demand data broadcast. IEEE/ACM Transactions on Networking, 7(6):846–860, 1999. [doi:10.1109/90.811450]

[3]   Nir Avrahami and Yossi Azar: Minimizing total flow time and total completion time with immediate dispatching. Algorithmica, 47:253–268, 2007. Preliminary version in SPAA’03. [doi:10.1007/s00453-006-0193-6]

[4]   Nikhil Bansal, Moses Charikar, Sanjeev Khanna, and Joseph (Seffi) Naor: Approximating the average response time in broadcast scheduling. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 215–221. SIAM, 2005.

[5]   Nikhil Bansal, Don Coppersmith, and Maxim Sviridenko: Improved approximation algorithms for broadcast scheduling. SIAM J. Comput., 38(3):1157–1174, 2008. Preliminary version in SODA’06. [doi:10.1137/060674417]

[6]   Nikhil Bansal, Ravishankar Krishnaswamy, and Viswanath Nagarajan: Better scalable algorithms for broadcast scheduling. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 324–335. Springer, 2010. [doi:10.1007/978-3-642-14165-2_28]

[7]   Nikhil Bansal and Kirk Pruhs: Server scheduling in the Lp norm: A rising tide lifts all boat. In Proc. 35th STOC, pp. 242–250. ACM Press, 2003. [doi:10.1145/780542.780580]

[8]   Amotz Bar-Noy, Randeep Bhatia, Joseph (Seffi) Naor, and Baruch Schieber: Minimizing service and operation costs of periodic scheduling. Math. Oper. Res., 27(3):518–544, 2002. [doi:10.1287/moor.27.3.518.314]

[9]   Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph (Seffi) Naor, Baruch Schieber, and Hadas Shachnai: Throughput maximization of real-time scheduling with batching. ACM Transactions on Algorithms, 5(2):18:1–18:17, 2009. [doi:10.1145/1497290.1497294]

[10]   Yair Bartal and S. Muthukrishnan: Minimizing maximum response time in scheduling broadcasts. In Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’00), pp. 558–559. SIAM, 2000. [ACM:338605]

[11]   Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan: Flow and stretch metrics for scheduling continuous job streams. In Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’98), pp. 270–279. SIAM, 1998. [ACM:314613.314715]

[12]   Michael A. Bender, Raphal Clifford, and Kostas Tsichlas: Scheduling algorithms for procrastinators. J. Scheduling, 11(2):95–104, 2008. [doi:10.1007/s10951-007-0038-4]

[13]   Michael A. Bender, S. Muthukrishnan, and Rajmohan Rajaraman: Approximation algorithms for average stretch scheduling. J. Scheduling, 7(3):195–222, 2004. [doi:10.1023/B:JOSH.0000019681.52701.8b]

[14]   Gennaro Boggia, Pietro Camarda, Luigi Mazzeo, and Marina Mongiello: Performance of batching schemes for multimedia-on-demand services. IEEE Transactions on Multimedia, 7(5):920–931, 2005. [doi:10.1109/TMM.2005.854383]

[15]   Alan Burns and Sanjoy Baruah: Sustainability in real-time scheduling. Journal of Computing Science and Engineering, 2(1):74–97, 2008. http://jcse.kiise.org/PublishedPaper/topic_abstract.asp?idx=15.

[16]   Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, and Prudence W. H. Wong: New results on on-demand broadcasting with deadline via job scheduling with cancellation. In Proc. 10th Ann. Internat. Computing and Combinatorics Conf. (COCOON’04), pp. 210–218. Springer Berlin / Heidelberg, 2004. [doi:10.1007/978-3-540-27798-9_24]

[17]   Jessica Chang, Thomas Erlebach, Renars Gailis, and Samir Khuller: Broadcast scheduling: Algorithms and complexity. ACM Transactions on Algorithms, 7(4):47:1–47:14, 2011. Preliminary version in SODA’08. [doi:10.1145/2000807.2000815]

[18]   Moses Charikar and Samir Khuller: A robust maximum completion time measure for scheduling. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 324–333. SIAM, 2006. [doi:10.1145/1109557.1109594]

[19]   Chandra Chekuri, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen, Benjamin Moseley, and Louiqa Raschid: New models and algorithms for throughput maximization in broadcast scheduling - (extended abstract). In Proc. 8th Workshop on Approximation and Online Algorithms (WAOA’10), pp. 71–82. Springer, 2010. [doi:10.1007/978-3-642-18318-8_7]

[20]   Chandra Chekuri, Ashish Goel, Sanjeev Khanna, and Amit Kumar: Multi-processor scheduling to minimize flow time with ϵ resource augmentation. In Proc. 36th STOC, pp. 363–372. ACM Press, 2004. [doi:10.1145/1007352.1007411]

[21]   Chandra Chekuri, Sungjin Im, and Benjamin Moseley: Longest wait first for broadcast scheduling [extended abstract]. In Proc. 7th Workshop on Approximation and Online Algorithms (WAOA’09), pp. 62–74. Springer, 2009. [doi:10.1007/978-3-642-12450-1_6]

[22]   Chandra Chekuri, Sungjin Im, and Benjamin Moseley: Minimizing maximum response time and delay factor in broadcast scheduling. In Proc. 17th Ann. European Symp. on Algorithms (ESA’09), pp. 444–455. Springer, 2009. [doi:10.1007/978-3-642-04128-0_40]

[23]   Chandra Chekuri and Benjamin Moseley: Online scheduling to minimize the maximum delay factor. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09). SIAM, 2009. [ACM:1496891]

[24]   Marek Chrobak, Christoph Drr, Wojciech Jawor, Łukasz Kowalik, and Maciej Kurowski: A note on scheduling equal-length jobs to maximize throughput. J. of Scheduling, 9(1):71–73, 2006. [doi:10.1007/s10951-006-5595-4]

[25]   Asit Dan, Dinkar Sitaram, and Perwez Shahabuddin: Dynamic batching policies for an on-demand video server. Multimedia Syst., 4(3):112–121, 1996. [doi:10.1007/s005300050016]

[26]   Rajat K. Deb: Optimal control of bulk queues with compound Poisson arrivals and batch service. Opsearch., 21:227–245, 1984.

[27]   Rajat K. Deb and Richard F. Serfozo: Optimal control of batch service queues. Adv. Appl. Prob., 5:340–361, 1973. [doi:10.2307/1426040]

[28]   Jeff Edmonds and Kirk Pruhs: Multicast pull scheduling: When fairness is fine. Algorithmica, 36(3):315–330, 2003. [doi:10.1007/s00453-003-1018-5]

[29]   Jeff Edmonds and Kirk Pruhs: A maiden analysis of longest wait first. ACM Trans. Algorithms, 1(1):14–32, 2005. [doi:10.1145/1077464.1077467]

[30]   Jeff Edmonds and Kirk Pruhs: Scalably scheduling processes with arbitrary speedup curves. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 685–692. SIAM, 2009. [doi:10.1145/1496770.1496845]

[31]   Thomas Erlebach and Alexander Hall: NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. Journal of Scheduling, 7:223–241, 2004. Preliminary version in SODA’02. [doi:10.1023/B:JOSH.0000019682.75022.96]

[32]   Rajiv Gandhi, Samir Khuller, Yoo-Ah Kim, and Yung-Chun (Justin) Wan: Algorithms for minimizing response time in broadcast scheduling. Algorithmica, 38(4):597–608, 2004. Preliminary version in IPCO’02. [doi:10.1007/s00453-003-1058-x]

[33]   Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan: Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324–360, 2006. [doi:10.1145/1147954.1147956]

[34]   Sungjin Im and Benjamin Moseley: An online scalable algorithm for average flow time in broadcast scheduling. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 1322–1333. SIAM, 2010. [ACM:1873601.1873708]

[35]   Bala Kalyanasundaram and Kirk Pruhs: Speed is as powerful as clairvoyance. J. ACM, 47(4):617–643, 2000. Preliminary version in FOCS’95. [doi:10.1145/347476.347479]

[36]   Bala Kalyanasundaram, Kirk R. Pruhs, and Mahendran Velauthapillai: Scheduling broadcasts in wireless networks. J. Scheduling, 4(6):339–354, 2001. Preliminary version in ESA’00. [doi:10.1002/jos.87]

[37]   David Karger, Cliff Stein, and Joel Wein: Scheduling algorithms. In Mikhail J. Atallah, editor, Handbook on Algorithms and Theory of Computation, chapter 35. CRC Press, 1999. [doi:10.1201/9781420049503-c36]

[38]   Samir Khuller and Yoo-Ah Kim: Equivalence of two linear programming relaxations for broadcast scheduling. Oper. Res. Lett., 32(5):473–478, 2004. [doi:10.1016/j.orl.2003.11.012]

[39]   Jae-Hoon Kim and Kyung-Yong Chwa: Scheduling broadcasts with deadlines. Theoret. Comput. Sci., 325(3):479–488, 2004. Preliminary version in COCOON’03. [doi:10.1016/j.tcs.2004.02.047]

[40]   Insup Lee, Joseph Y-T. Leung, and Sang H. Son, editors. Handbook of Real-Time and Embedded Systems. CRC Press, 2007. [doi:10.1201/9781420011746]

[41]   Kirk Pruhs: Competitive online scheduling for server systems. SIGMETRICS Perform. Eval. Rev., 34(4):52–58, 2007. [doi:10.1145/1243401.1243411]

[42]   Kirk Pruhs, Jiř Sgall, and Eric Torng: Online scheduling. In Joseph Y-T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, 2004.

[43]   Kirk R. Pruhs and Patchrawat Uthaisombut: A comparison of multicast pull models. Algorithmica, 42(3-4):289–307, 2005. Preliminary version in ESA’02. [doi:10.1007/s00453-005-1170-1]

[44]   Jiř Sgall: On-line scheduling. In Developments from a June 1996 seminar on Online algorithms, pp. 196–231. Springer-Verlag, 1998. [ACM:723918]

[45]    Reha Uzsoy: Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10):2685–2708, 1995. [doi:10.1080/00207549508904839]

[46]   Feifeng Zheng, Stanley P. Y. Fung, Wun-Tat Chan, Francis Y. L. Chin, Chung Keung Poon, and Prudence W. H. Wong: Improved on-line broadcast scheduling with deadlines. In Proc. 12th Ann. Internat. Computing and Combinatorics Conf. (COCOON’06), pp. 320–329. Springer, 2006. [doi:10.1007/11809678_34]