{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T16:43:08Z","timestamp":1781714588675,"version":"3.54.5"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,28]],"date-time":"2016-10-28T00:00:00Z","timestamp":1477612800000},"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":["J Sched"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10951-016-0500-2","type":"journal-article","created":{"date-parts":[[2016,10,28]],"date-time":"2016-10-28T07:55:19Z","timestamp":1477641319000},"page":"35-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Energy-efficient scheduling and routing via randomized rounding"],"prefix":"10.1007","volume":"21","author":[{"given":"Evripidis","family":"Bampis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Kononov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios","family":"Letsios","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giorgio","family":"Lucarelli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,10,28]]},"reference":[{"key":"500_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, K., Li, J., Lu, K., & Moseley, B. (2016). Scheduling parallel DAG jobs online to minimize average flow time. In SODA, (pp. 176\u2013189).","DOI":"10.1137\/1.9781611974331.ch14"},{"key":"500_CR2","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1735223.1735245","volume":"53","author":"S Albers","year":"2010","unstructured":"Albers, S. (2010). Energy-efficient algorithms. Communications of ACM, 53, 86\u201396.","journal-title":"Communications of ACM"},{"key":"500_CR3","unstructured":"Albers, S. (2011). Algorithms for dynamic speed scaling. In STACS, (pp. 1\u201311)."},{"key":"500_CR4","doi-asserted-by":"crossref","unstructured":"Albers, S., Antoniadis, A., & Greiner, G. (2011). On multi-processor speed scaling with migration: extended abstract. In SPAA (pp. 279\u2013288). ACM","DOI":"10.1145\/1989493.1989539"},{"key":"500_CR5","doi-asserted-by":"crossref","unstructured":"Albers, S., M\u00fcller, F., & Schmelzer, S. (2007). Speed scaling on parallel processors. In SPAA (pp. 289\u2013298). ACM.","DOI":"10.1145\/1248377.1248424"},{"key":"500_CR6","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1109\/TNET.2011.2159864","volume":"20","author":"M Andrews","year":"2012","unstructured":"Andrews, M., Anta, A. F., Zhang, L., & Zhao, W. (2012). Routing for power minimization in the speed scaling model. IEEE\/ACM Transaction on Networking, 20, 285\u2013294.","journal-title":"IEEE\/ACM Transaction on Networking"},{"key":"500_CR7","doi-asserted-by":"crossref","unstructured":"Andrews, M., Antonakopoulos, S., & Zhang, L. (2010). Minimum-cost network design with (dis)economies of scale. In FOCS (pp. 585\u2013592).","DOI":"10.1109\/FOCS.2010.61"},{"key":"500_CR8","doi-asserted-by":"crossref","unstructured":"Angel, E., Bampis, E., Kacem, F., & Letsios, D. (2012). Speed scaling on parallel processors with migration. In Euro-Par, volume 7484 of LNCS, (pp. 128\u2013140).","DOI":"10.1007\/978-3-642-32820-6_15"},{"key":"500_CR9","doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Huang, C.-C. (2012). Non-preemptive speed scaling. In SWAT, volume 7357 of LNCS (pp. 249\u2013260). Springer.","DOI":"10.1007\/978-3-642-31155-0_22"},{"key":"500_CR10","doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Im, S., Krishnaswamy, R., Moseley, B., Nagarajan, V., Pruhs, K., & Stein, C. (2014). Hallucination helps: Energy efficient virtual circuit routing. In SODA (pp. 1141\u20131153).","DOI":"10.1137\/1.9781611973402.84"},{"key":"500_CR11","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Kutten, S., & Peleg, D. (1992). Competitive distributed job scheduling (Extended abstract). In STOC (pp. 571\u2013580).","DOI":"10.1145\/129712.129768"},{"key":"500_CR12","doi-asserted-by":"crossref","unstructured":"Bampis, E., Chau, V., Letsios, D., Lucarelli, G., Milis, I., & Zois, G. (2014) Energy efficient scheduling of mapreduce jobs. In Euro-Par, volume 8632 of LNCS (pp. 198\u2013209). Springer.","DOI":"10.1007\/978-3-319-09873-9_17"},{"key":"500_CR13","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.dam.2014.10.007","volume":"181","author":"E Bampis","year":"2015","unstructured":"Bampis, E., Kononov, A., Letsios, D., Lucarelli, G., & Nemparis, I. (2015). From preemptive to non-preemptive speed-scaling scheduling. Discrete Applied Mathematics, 181, 11\u201320.","journal-title":"Discrete Applied Mathematics"},{"key":"500_CR14","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.tcs.2015.02.020","volume":"579","author":"E Bampis","year":"2015","unstructured":"Bampis, E., Letsios, D., & Lucarelli, G. (2015). Green scheduling, flows and matchings. Theoretical Computer Science, 579, 126\u2013136.","journal-title":"Theoretical Computer Science"},{"key":"500_CR15","doi-asserted-by":"crossref","unstructured":"Bampis, E., Letsios, D., & Lucarelli, G. (2014). A note on multiprocessor speed scaling with precedence constraints. In SPAA (pp. 138\u2013142). ACM","DOI":"10.1145\/2612669.2612672"},{"issue":"5","key":"500_CR16","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/j.dam.2010.11.015","volume":"159","author":"P Baptiste","year":"2011","unstructured":"Baptiste, P., Carlier, J., Kononov, A., Queyranne, M., Sevastyanov, S., & Sviridenko, M. (2011). Properties of optimal schedules in preemptive shop scheduling. Discrete Applied Mathematics, 159(5), 272\u2013280.","journal-title":"Discrete Applied Mathematics"},{"key":"500_CR17","first-page":"185","volume":"30","author":"D Berend","year":"2010","unstructured":"Berend, D., & Tassa, T. (2010). Improved bounds on Bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics, 30, 185\u2013205.","journal-title":"Probability and Mathematical Statistics"},{"key":"500_CR18","doi-asserted-by":"crossref","unstructured":"Bingham, B. D., & Greenstreet, M. R. (2008). Energy optimal scheduling on multiprocessors with migration. In ISPA (pp. 153\u2013161). IEEE.","DOI":"10.1109\/ISPA.2008.128"},{"key":"500_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2010\/540159","volume":"18","author":"AR Brodtkorb","year":"2010","unstructured":"Brodtkorb, A. R., Dyken, C., Hagen, T. R., Hjelmervik, J. M., & Storaasli, O. O. (2010). State-of-the-art in heterogeneous computing. Scientific Programming, 18, 1\u201333.","journal-title":"Scientific Programming"},{"key":"500_CR20","unstructured":"Deng, X., Liu, H.-N., & Xiao, B. (1990). Deterministic load balancing in computer networks. In SPDP (pp. 50\u201357)."},{"key":"500_CR21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10951-015-0463-8","volume":"19","author":"MET Gerards","year":"2016","unstructured":"Gerards, M. E. T., Hurink, J. L., & H\u00f6lzenspies, P. K. F. (2016). A survey of offline algorithms for energy minimization under deadline constraints. Journal of Scheduling, 19, 3\u201319.","journal-title":"Journal of Scheduling"},{"key":"500_CR22","doi-asserted-by":"crossref","unstructured":"Greiner, G., Nonner, T., & Souza, A. (2009). The bell is ringing in speed-scaled multiprocessor scheduling. In SPAA (pp. 11\u201318). ACM.","DOI":"10.1145\/1583991.1583996"},{"key":"500_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimizations","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., & Schrijver, A. (1993). Geometric algorithms and combinatorial optimizations (2nd ed.). Berlin: Springer.","edition":"2"},{"key":"500_CR24","doi-asserted-by":"crossref","unstructured":"Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., & Pruhs, K. (2012). Scheduling heterogeneous processors isn\u2019t as easy as you think. In SODA (pp. 1242\u20131253).","DOI":"10.1137\/1.9781611973099.98"},{"key":"500_CR25","unstructured":"Gupta, A., Krishnaswamy, R., Pruhs, K. (2012). Online primal-dual for non-linear optimization with applications to speed scaling. In WAOA, volume 7846 of LNCS (pp. 173\u2013186). Springer."},{"key":"500_CR26","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1214\/aoms\/1177728178","volume":"27","author":"W Hoeffding","year":"1956","unstructured":"Hoeffding, W. (1956). On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27, 713\u2013721.","journal-title":"Annals of Mathematical Statistics"},{"key":"500_CR27","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1991","unstructured":"Raghavan, P., & Thompson, C. D. (1991). Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7, 365\u2013374.","journal-title":"Combinatorica"},{"key":"500_CR28","doi-asserted-by":"crossref","unstructured":"Svensson, O. (2011). Santa claus schedules jobs on unrelated machines. In STOC (pp. 617\u2013626).","DOI":"10.1145\/1993636.1993718"},{"key":"500_CR29","doi-asserted-by":"crossref","unstructured":"Wierman, A., Andrew, L. L. H., & Tang, A. (2009). Power-aware speed scaling in processor sharing systems. In INFOCOM (pp. 2007\u20132015).","DOI":"10.1109\/INFCOM.2009.5062123"},{"key":"500_CR30","doi-asserted-by":"crossref","unstructured":"Yao, F., Demers, A., & Shenker, S. (1995). A scheduling model for reduced CPU energy. In FOCS (pp. 374\u2013382).","DOI":"10.1109\/SFCS.1995.492493"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-016-0500-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0500-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-016-0500-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T03:33:14Z","timestamp":1518492794000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-016-0500-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,28]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["500"],"URL":"https:\/\/doi.org\/10.1007\/s10951-016-0500-2","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,28]]}}}