{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:00Z","timestamp":1763468160716},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_64","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"755-766","source":"Crossref","is-referenced-by-count":7,"title":["Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling"],"prefix":"10.1007","author":[{"given":"Kim Thang","family":"Nguyen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"64_CR1","doi-asserted-by":"crossref","unstructured":"Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1228\u20131241 (2012)","DOI":"10.1137\/1.9781611973099.97"},{"issue":"2","key":"64_CR2","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":"64_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.-L.: Weighted flow time does not admit o(1)-competitive algorithms. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 1238\u20131244 (2009)","DOI":"10.1137\/1.9781611973068.134"},{"key":"64_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-540-70575-8_34","volume-title":"Automata, Languages and Programming","author":"N. Bansal","year":"2008","unstructured":"Bansal, N., Chan, H.-L., Lam, T.-W., Lee, L.-K.: Scheduling for speed bounded processors. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 409\u2013420. Springer, Heidelberg (2008)"},{"key":"64_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.-L., Pruhs, K.: Speed scaling with an arbitrary power function. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 693\u2013701 (2009)","DOI":"10.1137\/1.9781611973068.76"},{"key":"64_CR6","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":"64_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. In: Proc. 51th Symposium on Foundations of Computer Science, pp. 407\u2013414 (2010)","DOI":"10.1109\/FOCS.2010.46"},{"key":"64_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-642-33090-2_14","volume-title":"Algorithms \u2013 ESA 2012","author":"N. Bansal","year":"2012","unstructured":"Bansal, N., Pruhs, K.: Weighted geometric set multi-cover via quasi-uniform sampling. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 145\u2013156. Springer, Heidelberg (2012)"},{"issue":"2-3","key":"64_CR9","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science\u00a03(2-3), 93\u2013263 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"64_CR10","doi-asserted-by":"crossref","unstructured":"Chadha, J.S., Garg, N., Kumar, A., Muralidhara, V.N.: A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. In: Proc. 41st ACM Symposium on Theory of Computing, pp. 679\u2013684 (2009)","DOI":"10.1145\/1536414.1536506"},{"issue":"3","key":"64_CR11","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s00453-010-9420-2","volume":"61","author":"H.-L. Chan","year":"2011","unstructured":"Chan, H.-L., Edmonds, J., Lam, T.W., Lee, L.-K., Marchetti-Spaccamela, A., Pruhs, K.: Nonclairvoyant speed scaling for flow and energy. Algorithmica\u00a061(3), 507\u2013517 (2011)","journal-title":"Algorithmica"},{"key":"64_CR12","unstructured":"Chan, S.-H., Lam, T.W., Lee, L.-K., Ting, H.-F., Zhang, P.: Non-clairvoyant scheduling for weighted flow time and energy on speed bounded processors. Chicago J. Theor. Comput. Sci. (2011)"},{"key":"64_CR13","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: Proc. 33rd ACM Symposium on Theory of Computing, pp. 84\u201393 (2001)","DOI":"10.1145\/380752.380778"},{"issue":"1","key":"64_CR14","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.\u00a0235(1), 109\u2013141 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"64_CR15","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 Transactions on Algorithms\u00a08(3), 28 (2012)","journal-title":"ACM Transactions on Algorithms"},{"key":"64_CR16","doi-asserted-by":"crossref","unstructured":"Fox, K., Korupolu, M.: Weighted flowtime on capacitated machines. In: Proc. 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 129\u2013143 (2013)","DOI":"10.1137\/1.9781611973105.10"},{"key":"64_CR17","doi-asserted-by":"crossref","unstructured":"Garg, N., Kumar, A.: Minimizing average flow-time: Upper and lower bounds. In: Proc. 48th Symposium on Foundations of Computer Science, pp. 603\u2013613 (2007)","DOI":"10.1109\/FOCS.2007.4389529"},{"key":"64_CR18","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Pruhs, K.: Online primal-dual for non-linear optimization with applications to speed scaling. In: Proc. 10th Workshop on Approximation and Online Algorithms, pp. 173\u2013186 (2012)","DOI":"10.1007\/978-3-642-38016-7_15"},{"key":"64_CR19","unstructured":"Im, S.: Online Scheduling Algorithms for Average Flow Time and its Variants. PhD thesis, University of Illinois at Urbana-Champaign (2012)"},{"issue":"2","key":"64_CR20","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"},{"key":"64_CR21","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B., Pruhs, K.: Online scheduling with general cost functions. In: Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1254\u20131265 (2012)","DOI":"10.1137\/1.9781611973099.99"},{"issue":"4","key":"64_CR22","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\u00a047(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"key":"64_CR23","doi-asserted-by":"crossref","unstructured":"Kling, P., Pietrzyk, P.: Profitable scheduling on multiple speed-scalable processors. In: Proc. 25th Symposium on Parallelism in Algorithms and Architectures (2013)","DOI":"10.1145\/2486159.2486183"},{"key":"64_CR24","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":"3","key":"64_CR25","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/s00453-012-9613-y","volume":"65","author":"T.W. Lam","year":"2013","unstructured":"Lam, T.W., Lee, L.-K., To, I.K., Wong, P.W.H.: Online speed scaling based on active job count to minimize flow plus energy. Algorithmica\u00a065(3), 605\u2013633 (2013)","journal-title":"Algorithmica"},{"issue":"1","key":"64_CR26","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.\u00a0130(1), 17\u201347 (1994)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:55:48Z","timestamp":1558011348000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}