{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T09:08:19Z","timestamp":1791104899172,"version":"4.1.0"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Intel's SpeedStep and AMD's PowerNOW technologies allow the Windows XP operating system to dynamically change the speed of the processor to prolong battery life. In this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed at which the job will be run. We give an online speed scaling algorithm that is $O(1)$-competitive for the objective of weighted flow time plus energy. This algorithm also allows us to efficiently construct an $O(1)$-approximate schedule for minimizing weighted flow time subject to an energy constraint.<\/jats:p>","DOI":"10.1137\/08072125x","type":"journal-article","created":{"date-parts":[[2009,10,9]],"date-time":"2009-10-09T18:22:58Z","timestamp":1255112578000},"page":"1294-1308","source":"Crossref","is-referenced-by-count":53,"title":["Speed Scaling for Weighted Flow Time"],"prefix":"10.1137","volume":"39","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cliff","family":"Stein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,10,9]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290686"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Bansal, H.L. Chan, and K. Pruhs,\n                      Speed scaling with an arbitrary power function\n                      , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2009, pp. 693\u2013701.","DOI":"10.1137\/1.9781611973068.76"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"N. Bansal, D. Bunde, H.L. Chan, and K. Pruhs,\n                      Average rate speed scaling\n                      , in Proceedings of the Latin American Theoretical Informatics Symposium (LATIN), 2008, pp. 240\u2013251.","DOI":"10.1007\/978-3-540-78773-0_21"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Bansal, H.L. Chan, K. Pruhs, and D. Rogozhnikov-Katz,\n                      Improved bounds for speed scaling in devices obeying the cube-root rule\n                      , in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci. 5555, Springer, Berlin, 2009, pp. 144\u2013155.","DOI":"10.1007\/978-3-642-02927-1_14"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206038"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.12.001"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/40.888701"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"D. Bunde,\n                      Power-aware scheduling for makespan and flow\n                      , in Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Cambridge, MA), 2006, pp. 190\u2013196.","DOI":"10.1145\/1148109.1148140"},{"key":"R9","unstructured":"H.L. Chan, W.T. Chan, T.W. Lam, L.K. Lee, K.S. Mak, and P. W. H. Wong,\n                      Energy efficient online deadline scheduling\n                      , in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2007, pp. 795\u2013804."},{"key":"R10","unstructured":"G. H. Hardy, J. E. Littlewood, and G. Polya,\n                      Inequalities\n                      , Cambridge University Press, Cambridge, UK, 1952."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067324"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. Labetoulle, E. Lawler, J. K. Lenstra, and A. Rinnooy Kan,\n                      Preemptive scheduling of uniform machines subject to release dates\n                      , in Progress in Combinatorial Optimization, Academic Press, Toronto, 1984, pp. 245\u2013261.","DOI":"10.1016\/B978-0-12-566780-7.50020-9"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/2.917539"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367078"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9070-1"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"F. Yao, A. Demers, and S. Shenker,\n                      A scheduling model for reduced cpu energy\n                      , in Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science (Milwaukee, WI), 1995, pp. 374\u2013382.","DOI":"10.1109\/SFCS.1995.492493"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/08072125X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:25Z","timestamp":1787337025000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/08072125X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,9]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/08072125X"],"URL":"https:\/\/doi.org\/10.1137\/08072125x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,9]]}}}