{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:49:51Z","timestamp":1764402591201,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642380150"},{"type":"electronic","value":"9783642380167"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38016-7_15","type":"book-chapter","created":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T17:58:58Z","timestamp":1367344738000},"page":"173-186","source":"Crossref","is-referenced-by-count":18,"title":["Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravishankar","family":"Krishnaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"15_CR1","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":"3","key":"15_CR2","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":"4","key":"15_CR3","doi-asserted-by":"publisher","first-page":"1294","DOI":"10.1137\/08072125X","volume":"39","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Pruhs, K., Stein, C.: Speed scaling for weighted flow time. SIAM J. Comput.\u00a039(4), 1294\u20131308 (2009)","journal-title":"SIAM J. Comput."},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Andrews, M., Antonakopoulos, S., Zhang, L.: Energy-aware scheduling algorithms for network stability. In: INFOCOM, pp. 1359\u20131367 (2011)","DOI":"10.1109\/INFCOM.2011.5934920"},{"issue":"2-3","key":"15_CR5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.S.: 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":"15_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S. Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)"},{"key":"15_CR7","unstructured":"Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 374\u2013382 (1995)"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Bansal, N., Kimbrel, T., Pruhs, K.: Speed scaling to manage energy and temperature. Journal of the ACM\u00a054(1) (2007)","DOI":"10.1145\/1206035.1206038"},{"issue":"4","key":"15_CR9","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s00453-009-9379-z","volume":"60","author":"N. Bansal","year":"2011","unstructured":"Bansal, N., Bunde, D.P., Chan, H.L., Pruhs, K.: Average rate speed scaling. Algorithmica\u00a060(4), 877\u2013889 (2011)","journal-title":"Algorithmica"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-02927-1_14","volume-title":"Automata, Languages and Programming","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Chan, H.-L., Pruhs, K., Katz, D.: Improved bounds for speed scaling in devices obeying the cube-root rule. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 144\u2013155. Springer, Heidelberg (2009)"},{"issue":"4","key":"15_CR11","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/1290672.1290686","volume":"3","author":"S. Albers","year":"2007","unstructured":"Albers, S., Fujiwara, H.: Energy-efficient algorithms for flow time minimization. ACM Transactions on Algorithms\u00a03(4), 49 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.L., Pruhs, K.: Speed scaling with an arbitrary power function. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 693\u2013701 (2009)","DOI":"10.1137\/1.9781611973068.76"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Lam, T., Lee, L., To, I., Wong, P.: Speed scaling functions based for flow time scheduling based on active job count. In: European Symposium on Algorithms, pp. 647\u2013659 (2008)","DOI":"10.1007\/978-3-540-87744-8_54"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Andrew, L.L.H., Lin, M., Wierman, A.: Optimality, fairness, and robustness in speed scaling designs. In: SIGMETRICS, pp. 37\u201348 (2010)","DOI":"10.1145\/1811099.1811044"},{"key":"15_CR15","unstructured":"Chan, H.L., Edmonds, J., Lam, T.W., Lee, L.K., Marchetti-Spaccamela, A., Pruhs, K.: Nonclairvoyant speed scaling for flow and energy. In: Symposium on Theoretical Aspects of Computer Science, pp. 255\u2013264 (2009)"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Chan, S.H., Lam, T.W., Lee, L.K.: Non-clairvoyant speed scaling for weighted flow time. In: European Symposium on Algorithms, pp. 23\u201335 (2010)","DOI":"10.1007\/978-3-642-15775-2_3"},{"issue":"3","key":"15_CR17","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM\u00a044(3), 486\u2013504 (1997)","journal-title":"Journal of the ACM"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Grove, E.F., Kao, M.Y., Krishnan, P., Vitter, J.S.: Load balancing in the Lp norm. In: IEEE Symposium on Foundations of Computer Science, pp. 383\u2013391 (1995)","DOI":"10.1109\/SFCS.1995.492494"},{"issue":"5","key":"15_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/1735223.1735245","volume":"53","author":"S. Albers","year":"2010","unstructured":"Albers, S.: Energy-efficient algorithms. Communications of the ACM\u00a053(5), 86\u201396 (2010)","journal-title":"Communications of the ACM"},{"key":"15_CR20","first-page":"972","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"I. Caragiannis","year":"2008","unstructured":"Caragiannis, I.: Better bounds for online load balancing on unrelated machines. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 972\u2013981. ACM, New York (2008)"},{"key":"15_CR21","first-page":"331","volume-title":"ACM Symposium on Theory of Computing","author":"Y. Azar","year":"2005","unstructured":"Azar, Y., Epstein, A.: Convex programming for scheduling unrelated parallel machines. In: ACM Symposium on Theory of Computing, pp. 331\u2013337. ACM, New York (2005)"},{"issue":"5","key":"15_CR22","first-page":"31","volume":"56","author":"V.S. Anil Kumar","year":"2009","unstructured":"Anil Kumar, V.S., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: A unified approach to scheduling on unrelated parallel machines. Journal of the ACM\u00a056(5), Art. 28, 31 (2009)","journal-title":"Journal of the ACM"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Andrews, M., Antonakopoulos, S., Zhang, L.: Minimum-cost network design with (dis)economies of scale. In: IEEE Symposium on Foundations of Computer Science, pp. 585\u2013592 (2010)","DOI":"10.1109\/FOCS.2010.61"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling jobs with varying parallelizability to reduce variance. In: ACM Symposium on Parallelism in Algorithms and Architectures, pp. 11\u201320 (2010)","DOI":"10.1145\/1810479.1810482"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: Online scalable algorithm for minimizing lk-norms of weighted flow time on unrelated machines. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 95\u2013108 (2011)","DOI":"10.1137\/1.9781611973082.8"},{"key":"15_CR26","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 (2012)","DOI":"10.1137\/1.9781611973099.97"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38016-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T07:35:37Z","timestamp":1745998537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38016-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642380150","9783642380167"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38016-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}