{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:29Z","timestamp":1740109289226,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T00:00:00Z","timestamp":1557532800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-BS02-0015","ANR-13-INFR-0001"],"award-info":[{"award-number":["ANR-11-BS02-0015","ANR-13-INFR-0001"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006289","name":"\u00c9lectricit\u00e9 de France","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006289","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00453-019-00583-8","type":"journal-article","created":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T14:58:38Z","timestamp":1557586718000},"page":"3391-3421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Primal\u2013Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow-Time Problems"],"prefix":"10.1007","volume":"81","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Lucarelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thang","family":"Nguyen Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,11]]},"reference":[{"key":"583_CR1","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"},{"key":"583_CR2","unstructured":"Antoniadis, A., Barcelo, N., Consuegra, M., Kling, P., Nugent, M., Pruhs, K., Scquizzato, M.: Efficient computation of optimal energy and fractional weighted flow trade-off schedules. In: STACS, vol. 25 of LIPIcs, pp. 63\u201374 (2014)"},{"key":"583_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":"583_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: Server scheduling in the weighted $$\\ell _p$$ norm. In: LATIN, vol. 2976 of LNCS, pp. 434\u2013443 (2004)","DOI":"10.1007\/978-3-540-24698-5_47"},{"key":"583_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. In: FOCS, pp. 407\u2013414 (2010)","DOI":"10.1109\/FOCS.2010.46"},{"issue":"3","key":"583_CR6","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. Discrete Algorithms 4(3), 339\u2013352 (2006)","journal-title":"J. Discrete Algorithms"},{"key":"583_CR7","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Huang, Z.: Primal dual gives almost optimal energy efficient online algorithms. In: SODA, pp. 1123\u20131140 (2014)","DOI":"10.1137\/1.9781611973402.83"},{"issue":"1","key":"583_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-3975(99)00186-3","volume":"235","author":"J Edmonds","year":"2000","unstructured":"Edmonds, J.: Scheduling in the dark. Theor. Comput. Sci. 235(1), 109\u2013141 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"583_CR9","doi-asserted-by":"publisher","first-page":"28","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 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"583_CR10","doi-asserted-by":"crossref","unstructured":"Fox, K., Im, S., Kulkarni, J., Moseley, B.: Online non-clairvoyant scheduling to simultaneously minimize all convex functions. In: APPROX-RANDOM, vol.8096 of LNCS, pp. 142\u2013157 (2013)","DOI":"10.1007\/978-3-642-40328-6_11"},{"key":"583_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling heterogeneous processors isn\u2019t as easy as you think. In: SODA, pp. 1242\u20131253 (2012)","DOI":"10.1137\/1.9781611973099.98"},{"key":"583_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Pruhs, K.: Nonclairvoyantly scheduling power-heterogeneous processors. In: Green Computing Conference, pp. 165\u2013173 (2010)","DOI":"10.1109\/GREENCOMP.2010.5598311"},{"key":"583_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Pruhs, K.: Online primal\u2013dual for non-linear optimization with applications to speed scaling. In: WAOA, vol. 7846 of LNCS, pp. 173\u2013186 (2012)","DOI":"10.1007\/978-3-642-38016-7_15"},{"key":"583_CR14","doi-asserted-by":"crossref","unstructured":"H\u00f6hn, W., Mestre, J., Wiese, A.: How unsplittable-flow-covering helps scheduling with job-dependent cost functions. In: ICALP, vol. 8572 of LNCS, pp. 625\u2013636 (2014)","DOI":"10.1007\/978-3-662-43948-7_52"},{"key":"583_CR15","doi-asserted-by":"crossref","unstructured":"Im, S., Kulkarni, J., Munagala, K.: Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In: STOC, pp. 313\u2013322 (2014)","DOI":"10.1145\/2591796.2591814"},{"key":"583_CR16","doi-asserted-by":"crossref","unstructured":"Im, S., Kulkarni, J., Munagala, K., Pruhs, K.: Selfishmigrate: a scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In: FOCS, pp. 531\u2013540 (2014)","DOI":"10.1109\/FOCS.2014.63"},{"issue":"2","key":"583_CR17","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/1998037.1998058","volume":"42","author":"S Im","year":"2011","unstructured":"Im, S., Moseley, B., Pruhs, K.: A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42(2), 83\u201397 (2011)","journal-title":"SIGACT News"},{"issue":"1","key":"583_CR18","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1137\/120902288","volume":"43","author":"S Im","year":"2014","unstructured":"Im, S., Moseley, B., Pruhs, K.: Online scheduling with general cost functions. SIAM J. Comput. 43(1), 126\u2013143 (2014)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"583_CR19","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. JACM 50(6), 795\u2013824 (2003)","journal-title":"JACM"},{"issue":"4","key":"583_CR20","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. JACM 47(4), 617\u2013643 (2000)","journal-title":"JACM"},{"issue":"1","key":"583_CR21","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","volume":"130","author":"R Motwani","year":"1994","unstructured":"Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. Theor. Comput. Sci. 130(1), 17\u201347 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"583_CR22","doi-asserted-by":"crossref","unstructured":"Nguyen, K.T.: Lagrangian duality in online scheduling with resource augmentation and speed scaling. In: ESA, vol. 8125 of LNCS, pp. 755\u2013766 (2013)","DOI":"10.1007\/978-3-642-40450-4_64"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00583-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00583-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00583-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T23:12:00Z","timestamp":1589065920000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00583-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,11]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["583"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00583-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,5,11]]},"assertion":[{"value":"22 February 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}