{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:46Z","timestamp":1740109306374,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T00:00:00Z","timestamp":1560470400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T00:00:00Z","timestamp":1560470400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1409130","CCF-0745761"],"award-info":[{"award-number":["CCF 1409130","CCF-0745761"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1008065","CCF-1348696"],"award-info":[{"award-number":["CCF-1008065","CCF-1348696"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE-AC05- 06OR23100."],"award-info":[{"award-number":["DE-AC05- 06OR23100."]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00453-019-00597-2","type":"journal-article","created":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T10:26:47Z","timestamp":1560508007000},"page":"3746-3764","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Non-clairvoyantly Scheduling to Minimize Convex Functions"],"prefix":"10.1007","volume":"81","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","published-online":{"date-parts":[[2019,6,14]]},"reference":[{"key":"597_CR1","doi-asserted-by":"crossref","unstructured":"Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1228\u20131241 (2012)","DOI":"10.1137\/1.9781611973099.97"},{"key":"597_CR2","doi-asserted-by":"crossref","unstructured":"Avrahami, N., Azar, Y.: Minimizing total flow time and total completion time with immediate dispatching. In: ACM Symposium on Parallel Algorithms and Architectures, pp. 11\u201318 (2003)","DOI":"10.1145\/777412.777415"},{"issue":"5","key":"597_CR3","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. 31(5), 1370\u20131382 (2002)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"597_CR4","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 52(2), 120\u2013133 (2004)","journal-title":"J. Algorithms"},{"key":"597_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.-L.: Weighted flow time does not admit o(1)-competitive algorithms. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1238\u20131244 (2009)","DOI":"10.1137\/1.9781611973068.134"},{"issue":"1","key":"597_CR6","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/2636916","volume":"11","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Krishnaswamy, R., Nagarajan, V.: Better scalable algorithms for broadcast scheduling. ACM Trans. Algorithms 11(1), 3:1\u20133:24 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"7","key":"597_CR7","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. 39(7), 3311\u20133335 (2010)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"597_CR8","doi-asserted-by":"publisher","first-page":"1684","DOI":"10.1137\/130911317","volume":"43","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. SIAM J. Comput. 43(5), 1684\u20131698 (2014)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"597_CR9","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 51(4), 517\u2013539 (2004)","journal-title":"J. ACM"},{"issue":"3","key":"597_CR10","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. J. Discret. Algorithms 4(3), 339\u2013352 (2006)","journal-title":"J. Discret. Algorithms"},{"key":"597_CR11","unstructured":"Bender, M.A., Chakrabarti, S., Muthukrishnan, S.: Flow and stretch metrics for scheduling continuous job streams. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 270\u2013279 (1998)"},{"key":"597_CR12","unstructured":"Borodin, A., El-Yaniv, R.: On ranomization in online computation. In: IEEE Conference on Computational Complexity, pp. 226\u2013238 (1997)"},{"issue":"4","key":"597_CR13","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. 34(4), 451\u2013458 (2006)","journal-title":"Oper. Res. Lett."},{"key":"597_CR14","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: ACM Symposium on Theory of Computing, pp. 363\u2013372 (2004)","DOI":"10.1145\/1007352.1007411"},{"issue":"1","key":"597_CR15","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 Comput. 8(1), 165\u2013195 (2012)","journal-title":"Theory Comput."},{"key":"597_CR16","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: ACM Symposium on Theory of Computing, pp. 84\u201393 (2001)","DOI":"10.1145\/380752.380778"},{"key":"597_CR17","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Im, S., Moseley, B.: Online scalable scheduling for the $$\\ell _k$$-norms of flow time without conservation of work. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 109\u2013119 (2011)","DOI":"10.1137\/1.9781611973082.9"},{"issue":"3","key":"597_CR18","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2229163.2229172","volume":"8","author":"J Edmonds","year":"2012","unstructured":"Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. ACM Trans. Algorithms 8(3), 28:1\u201328:10 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"597_CR19","doi-asserted-by":"crossref","unstructured":"Fox, K., Moseley, B.: Online scheduling on identical machines using SRPT. In: ACM-SIAM Symposium on Discrete Algorithms (2011)","DOI":"10.1137\/1.9781611973082.10"},{"key":"597_CR20","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: An online scalable algorithm for minimizing $$\\ell _k$$-norms of weighted flow time on unrelated machines. In: ACM-SIAM Symposium on Discrete Algorithms (2011)","DOI":"10.1137\/1.9781611973082.8"},{"key":"597_CR21","unstructured":"Im, S., Moseley, B.: Fair scheduling via iterative quasi-uniform sampling. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, 16-19 January, pp. 2601\u20132615, (2017)"},{"key":"597_CR22","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B., Pruhs, K.: Online scheduling with general cost functions. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1254\u20131265 (2012)","DOI":"10.1137\/1.9781611973099.99"},{"issue":"4","key":"597_CR23","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 47(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"issue":"5","key":"597_CR24","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/1552285.1552289","volume":"56","author":"VSA Kumar","year":"2009","unstructured":"Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: A unified approach to scheduling on unrelated parallel machines. J. ACM 56(5), 28 (2009)","journal-title":"J. ACM"},{"issue":"6","key":"597_CR25","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. 73(6), 875\u2013891 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"597_CR26","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"CA Phillips","year":"2002","unstructured":"Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2), 163\u2013200 (2002)","journal-title":"Algorithmica"},{"key":"597_CR27","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Online Scheduling (2004)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00597-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00597-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00597-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,12]],"date-time":"2020-06-12T23:18:16Z","timestamp":1592003896000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00597-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,14]]},"references-count":27,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["597"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00597-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,6,14]]},"assertion":[{"value":"21 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}