{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:20Z","timestamp":1725745280359},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_11","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T13:17:34Z","timestamp":1376659054000},"page":"142-157","source":"Crossref","is-referenced-by-count":4,"title":["Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions"],"prefix":"10.1007","author":[{"given":"Kyle","family":"Fox","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sungjin","family":"Im","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Janardhan","family":"Kulkarni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B., Pruhs, K.: Online scheduling with general cost functions. In: SODA, pp. 1254\u20131265 (2012)","DOI":"10.1137\/1.9781611973099.99"},{"key":"11_CR2","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Online Scheduling. In: Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004)"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.L.: Weighted flow time does not admit o(1)-competitive algorithms. In: SODA, pp. 1238\u20131244 (2009)","DOI":"10.1137\/1.9781611973068.134"},{"key":"11_CR4","unstructured":"Bender, M.A., Chakrabarti, S., Muthukrishnan, S.: Flow and stretch metrics for scheduling continuous job streams. In: SODA, pp. 270\u2013279 (1998)"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"165","DOI":"10.4086\/toc.2012.v008a007","volume":"8","author":"C. Chekuri","year":"2012","unstructured":"Chekuri, C., Im, S., Moseley, B.: Online scheduling to minimize maximum response time and maximum delay factor. Theory of Computing\u00a08(1), 165\u2013195 (2012)","journal-title":"Theory of Computing"},{"issue":"4","key":"11_CR6","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. Journal of the ACM\u00a047(4), 617\u2013643 (2000)","journal-title":"Journal of the ACM"},{"issue":"2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"C.A. Phillips","year":"2002","unstructured":"Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. Algorithmica\u00a032(2), 163\u2013200 (2002)","journal-title":"Algorithmica"},{"issue":"3","key":"11_CR8","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.jda.2005.12.001","volume":"4","author":"L. Becchetti","year":"2006","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Pruhs, K.: Online weighted flow time and deadline scheduling. Journal of Discrete Algorithms\u00a04(3), 339\u2013352 (2006)","journal-title":"Journal of Discrete Algorithms"},{"issue":"7","key":"11_CR9","doi-asserted-by":"publisher","first-page":"3311","DOI":"10.1137\/090772228","volume":"39","author":"N. Bansal","year":"2010","unstructured":"Bansal, N., Pruhs, K.: Server scheduling to balance priorities, fairness, and average quality of service. SIAM J. Comput.\u00a039(7), 3311\u20133335 (2010)","journal-title":"SIAM J. Comput."},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Im, S., Moseley, B.: Online scalable scheduling for the \u2113\n                    k\n                  -norms of flow time without conservation of work. In: ACM-SIAM Symposium on Discrete Algorithms (2011)","DOI":"10.1137\/1.9781611973082.9"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: An online scalable algorithm for minimizing \u2113\n                    k\n                  -norms of weighted flow time on unrelated machines. In: ACM-SIAM Symposium on Discrete Algorithms (2011)","DOI":"10.1137\/1.9781611973082.8"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: SODA, pp. 1228\u20131241 (2012)","DOI":"10.1137\/1.9781611973099.97"},{"issue":"2","key":"11_CR13","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.jalgor.2004.02.003","volume":"52","author":"Y. Azar","year":"2004","unstructured":"Azar, Y., Epstein, L., Richter, Y., Woeginger, G.J.: All-norm approximation algorithms. J. Algorithms\u00a052(2), 120\u2013133 (2004)","journal-title":"J. Algorithms"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: A unified approach to scheduling on unrelated parallel machines. J. ACM\u00a056(5) (2009)","DOI":"10.1145\/1552285.1552289"},{"issue":"6","key":"11_CR15","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1016\/j.jcss.2006.10.018","volume":"73","author":"S. Leonardi","year":"2007","unstructured":"Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. J. Comput. Syst. Sci.\u00a073(6), 875\u2013891 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Goel, A., Khanna, S., Kumar, A.: Multi-processor scheduling to minimize flow time with epsilon resource augmentation. In: STOC, pp. 363\u2013372 (2004)","DOI":"10.1145\/1007352.1007411"},{"issue":"5","key":"11_CR17","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S009753970037446X","volume":"31","author":"B. Awerbuch","year":"2002","unstructured":"Awerbuch, B., Azar, Y., Leonardi, S., Regev, O.: Minimizing the flow time without migration. SIAM J. Comput.\u00a031(5), 1370\u20131382 (2002)","journal-title":"SIAM J. Comput."},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Avrahami, N., Azar, Y.: Minimizing total flow time and total completion time with immediate dispatching. In: SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 11\u201318 (2003)","DOI":"10.1145\/777412.777415"},{"issue":"4","key":"11_CR19","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/1008731.1008732","volume":"51","author":"L. Becchetti","year":"2004","unstructured":"Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM\u00a051(4), 517\u2013539 (2004)","journal-title":"J. ACM"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: STOC, pp. 84\u201393 (2001)","DOI":"10.1145\/380752.380778"},{"issue":"4","key":"11_CR21","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.orl.2005.07.005","volume":"34","author":"C. Bussema","year":"2006","unstructured":"Bussema, C., Torng, E.: Greedy multiprocessor server scheduling. Oper. Res. Lett.\u00a034(4), 451\u2013458 (2006)","journal-title":"Oper. Res. Lett."},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Fox, K., Moseley, B.: Online scheduling on identical machines using srpt. In: SODA, pp. 120\u2013128 (2011)","DOI":"10.1137\/1.9781611973082.10"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 685\u2013692 (2009)","DOI":"10.1137\/1.9781611973068.75"},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-14165-2_28","volume-title":"Automata, Languages and Programming","author":"N. Bansal","year":"2010","unstructured":"Bansal, N., Krishnaswamy, R., Nagarajan, V.: Better scalable algorithms for broadcast scheduling. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 324\u2013335. Springer, Heidelberg (2010)"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. In: IEEE Symposium on the Foundations of Computer Science, pp. 407\u2013414 (2010)","DOI":"10.1109\/FOCS.2010.46"},{"key":"11_CR26","unstructured":"Borodin, A., El-Yaniv, R.: On randomization in online computation. In: IEEE Conference on Computational Complexity, pp. 226\u2013238 (1997)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:42:48Z","timestamp":1558028568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}