{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T09:08:16Z","timestamp":1791104896271,"version":"4.1.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CNS-0325353, CCF-0514058, IIS-0534531, CCF-083558, CCF-1115575"],"award-info":[{"award-number":["CNS-0325353, CCF-0514058, IIS-0534531, CCF-083558, CCF-1115575"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0325353, CCF-0514058, IIS-0534531, CCF-083558, CCF-1115575"],"award-info":[{"award-number":["CNS-0325353, CCF-0514058, IIS-0534531, CCF-083558, CCF-1115575"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CNS-0325353, CCF-0514058, IIS-0534531, CCF-083558, CCF-1115575"],"award-info":[{"award-number":["CNS-0325353, CCF-0514058, IIS-0534531, CCF-083558, CCF-1115575"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>This article initiates a theoretical investigation into online scheduling problems with speed scaling where the allowable speeds may be discrete, and the power function may be arbitrary, and develops algorithmic analysis techniques for this setting. We show that a natural algorithm, which uses Shortest Remaining Processing Time for scheduling and sets the power to be one more than the number of unfinished jobs, is 3-competitive for the objective of total flow time plus energy. We also show that another natural algorithm, which uses Highest Density First for scheduling and sets the power to be the fractional weight of the unfinished jobs, is a 2-competitive algorithm for the objective of fractional weighted flow time plus energy.<\/jats:p>","DOI":"10.1145\/2438645.2438650","type":"journal-article","created":{"date-parts":[[2013,3,19]],"date-time":"2013-03-19T13:34:23Z","timestamp":1363700063000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Speed Scaling with an Arbitrary Power Function"],"prefix":"10.1145","volume":"9","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ho-Leung","family":"Chan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[{"name":"University of Pittsburgh"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290686"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639562.1639576"},{"key":"e_1_2_1_3_1","volume-title":"-L","author":"Bansal N.","year":"2009","unstructured":"Bansal , N. and Chan , H . -L . 2009 . Weighted flow time does not admit O(1)-competitive algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 1238--1244. Bansal, N. and Chan, H.-L. 2009. Weighted flow time does not admit O(1)-competitive algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 1238--1244."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_34"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 805--813","author":"Bansal N.","unstructured":"Bansal , N. , Pruhs , K. , and Stein , C . 2007. Speed scaling for weighted flow time . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 805--813 . Bansal, N., Pruhs, K., and Stein, C. 2007. Speed scaling for weighted flow time. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 805--813."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2008.46"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/GREENCOMP.2010.5598311"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Colloquium on Automata Languages and Programming. 312--323","author":"Gupta A.","unstructured":"Gupta , A. , Krishnaswamy , R. , and Pruhs , K . 2010b. Scalably scheduling power-heterogeneous processors . In Proceedings of the International Colloquium on Automata Languages and Programming. 312--323 . Gupta, A., Krishnaswamy, R., and Pruhs, K. 2010b. Scalably scheduling power-heterogeneous processors. In Proceedings of the International Colloquium on Automata Languages and Programming. 312--323."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_54"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/050629434"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243401.1243411"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367078"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2438645.2438650","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2438645.2438650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:29Z","timestamp":1750235729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2438645.2438650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2438645.2438650"],"URL":"https:\/\/doi.org\/10.1145\/2438645.2438650","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2010-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}