{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:20Z","timestamp":1759637840633,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_4","type":"book-chapter","created":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T21:40:34Z","timestamp":1441057234000},"page":"35-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Primal-Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow Time Problems"],"prefix":"10.1007","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":"Kim Thang","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"4_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":"4_CR2","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Lucarelli, G., Thang, N.K.: Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems. CoRR, abs\/1502.03946 (2015)","DOI":"10.1007\/978-3-662-48350-3_4"},{"key":"4_CR3","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. LIPIcs, vol.\u00a025, pp. 63\u201374 (2014)"},{"key":"4_CR4","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":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/978-3-540-24698-5_47","volume-title":"LATIN 2004: Theoretical Informatics","author":"N. Bansal","year":"2004","unstructured":"Bansal, N., Pruhs, K.R.: Server scheduling in the weighted \u2113\n                    p\n                   norm. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 434\u2013443. Springer, Heidelberg (2004)"},{"key":"4_CR6","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":"4_CR7","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\u00a04(3), 339\u2013352 (2006)","journal-title":"J. Discrete Algorithms"},{"key":"4_CR8","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"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-642-40328-6_11","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K. Fox","year":"2013","unstructured":"Fox, K., Im, S., Kulkarni, J., Moseley, B.: Online non-clairvoyant scheduling to simultaneously minimize all convex functions. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol.\u00a08096, pp. 142\u2013157. Springer, Heidelberg (2013)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-642-38016-7_15","volume-title":"Approximation and Online Algorithms","author":"A. Gupta","year":"2013","unstructured":"Gupta, A., Krishnaswamy, R., Pruhs, K.: Online primal-dual for non-linear optimization with applications to speed scaling. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol.\u00a07846, pp. 173\u2013186. Springer, Heidelberg (2013)"},{"key":"4_CR11","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":"4_CR12","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":"4_CR13","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\u00a042(2), 83\u201397 (2011)","journal-title":"SIGACT News"},{"issue":"1","key":"4_CR14","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 Journal on Computing\u00a043(1), 126\u2013143 (2014)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"4_CR15","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"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/978-3-642-40450-4_64","volume-title":"Algorithms \u2013 ESA 2013","author":"K.T. Nguyen","year":"2013","unstructured":"Nguyen, K.T.: Lagrangian duality in online scheduling with resource augmentation and speed scaling. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 755\u2013766. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T15:59:24Z","timestamp":1559231964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"12 November 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}