Minimizing Maximum Flow-Time on Related Machines

by Nikhil Bansal and Bouke Cloostermans

Theory of Computing, Volume 12(14), pp. 1-14, 2016

Bibliography with links to cited articles

[1]   Susanne Albers: Online scheduling. In Introduction to Scheduling (Yves Robert and Frédéric Vivien, eds.), chapter 3, pp. 51–73. Chapman and Hall/CRC Press, 2010. Version available on author’s website. [doi:10.1201/9781420072747-c3]

[2]   Christoph Ambühl and Monaldo Mastrolilli: On-line scheduling to minimize max flow time: an optimal preemptive algorithm. Oper. Res. Lett., 33(6):597–602, 2005. [doi:10.1016/j.orl.2004.10.006]

[3]   S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, and Amit Kumar: Minimizing maximum (weighted) flow-time on related and unrelated machines. In Proc. 40th Internat. Colloq. on Automata, Languages and Programming (ICALP’13), pp. 13–24. Springer, 2013. [doi:10.1007/978-3-642-39206-1_2]

[4]   S. Anand, Naveen Garg, and Amit Kumar: Resource augmentation for weighted flow-time explained by dual fitting. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp. 1228–1241. ACM Press, 2012. ACM DL.

[5]   Yossi Azar: On-line load balancing. In Online Algorithms, volume 1442 of LNCS, pp. 178–195. Springer, 1998. [doi:10.1007/BFb0029569]

[6]   Yossi Azar, Bala Kalyanasundaram, Serge A. Plotkin, Kirk Pruhs, and Orli Waarts: On-line load balancing of temporary tasks. J. Algorithms, 22(1):93–110, 1997. Preliminary version in WADS’93. [doi:10.1006/jagm.1995.0799]

[7]    Nikhil Bansal and Bouke Cloostermans: Minimizing maximum flow-time on related machines. In Proc. 18th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’15), pp. 85–95, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.85]

[8]   Nikhil Bansal and Janardhan Kulkarni: Minimizing flow-time on unrelated machines. In Proc. 47th STOC, pp. 851–860. ACM Press, 2015. [doi:10.1145/2746539.2746601, arXiv:1401.7284]

[9]   Niv Buchbinder and Joseph Naor: The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93–263, 2009. Preliminary version in FOCS’06. [doi:10.1561/0400000024]

[10]   Chandra Chekuri, Sungjin Im, and Benjamin Moseley: Online scheduling to minimize maximum response time and maximum delay factor. Theory of Computing, 8(7):165–195, 2012. Preliminary version in ESA’09. [doi:10.4086/toc.2012.v008a007, arXiv:0906.2048]

[11]   Yookun Cho and Sartaj Sahni: Bounds for list schedules on uniform processors. SIAM J. Comput., 9(1):91–103, 1980. [doi:10.1137/0209007]

[12]   Naveen Garg: Minimizing average flow-time. In Efficient Algorithms, Essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday, pp. 187–198, 2009. Preliminary version in FOCS’07. [doi:10.1007/978-3-642-03456-5_13]

[13]   Sungjin Im, Benjamin Moseley, and Kirk Pruhs: A tutorial on amortized local competitiveness in online scheduling. ACM SIGACT News, 42(2):83–97, 2011. [doi:10.1145/1998037.1998058]

[14]   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]

[15]   Monaldo Mastrolilli: Scheduling to minimize max flow time: Off-line and on-line algorithms. Internat. J. Foundat. Comput. Sci., 15(2):385–401, 2004. Preliminary version in FCT’03. [doi:10.1142/S0129054104002480]

[16]   Kirk Pruhs, Jiří Sgall, and Eric Torng: Online scheduling. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis (Joseph Y-T. Leung, ed.), chapter 15. CRC Press, 2004. Available at CRC Press.