{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:24:21Z","timestamp":1759335861677,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T00:00:00Z","timestamp":1671148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["691672"],"award-info":[{"award-number":["691672"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Electricity cost is a dominant and rapidly growing expense in data centers. Unfortunately, much of the consumed energy is wasted, because servers are idle for extended periods of time. We study a capacity management problem that dynamically right-sizes a data center, matching the number of active servers with the varying demand for computing capacity. We resort to a data-center optimization problem introduced by Lin, Wierman, Andrew, and Thereska\u00a0[\n            <jats:xref ref-type=\"bibr\">25<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">27<\/jats:xref>\n            ] that, over a time horizon, minimizes a combined objective function consisting of operating cost, modeled by a sequence of convex functions, and server switching cost. All prior work addresses a continuous setting in which the number of active servers, at any time, may take a fractional value.\n          <\/jats:p>\n          <jats:p>\n            In this article, we investigate for the first time the discrete data-center optimization problem where the number of active servers, at any time, must be integer valued. Thereby, we seek truly feasible solutions. First, we show that the offline problem can be solved in polynomial time. Our algorithm relies on a new, yet intuitive graph theoretic model of the optimization problem and performs binary search in a layered graph. Second, we study the online problem and extend the algorithm\n            <jats:italic>Lazy Capacity Provisioning<\/jats:italic>\n            (LCP) by Lin et\u00a0al.\u00a0[\n            <jats:xref ref-type=\"bibr\">25<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">27<\/jats:xref>\n            ] to the discrete setting. We prove that LCP is 3-competitive. Moreover, we show that no deterministic online algorithm can achieve a competitive ratio smaller than\u00a03. Hence, while LCP does not attain an optimal competitiveness in the continuous setting, it does so in the discrete problem examined here. We prove that the lower bound of\u00a03 also holds in a problem variant with more restricted operating cost functions, introduced by Lin et\u00a0al.\u00a0[\n            <jats:xref ref-type=\"bibr\">25<\/jats:xref>\n            ].\n          <\/jats:p>\n          <jats:p>\n            In addition, we develop a randomized online algorithm that is 2-competitive against an oblivious adversary. It is based on the algorithm of Bansal et\u00a0al.\u00a0[\n            <jats:xref ref-type=\"bibr\">7<\/jats:xref>\n            ] (a deterministic, 2-competitive algorithm for the continuous setting) and uses randomized rounding to obtain an integral solution. Moreover, we prove that 2 is a lower bound for the competitive ratio of randomized online algorithms, so our algorithm is optimal. We prove that the lower bound still holds for the more restricted model.\n          <\/jats:p>\n          <jats:p>\n            Finally, we address the continuous setting and give a lower bound of\u00a02 on the best competitiveness of online algorithms. This matches an upper bound by Bansal et\u00a0al.\u00a0[\n            <jats:xref ref-type=\"bibr\">7<\/jats:xref>\n            ]. A lower bound of\u00a02 was also shown by Antoniadis and Schewior\u00a0[\n            <jats:xref ref-type=\"bibr\">4<\/jats:xref>\n            ]. We develop an independent proof that extends to the scenario with more restricted operating cost.\n          <\/jats:p>","DOI":"10.1145\/3565513","type":"journal-article","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T12:08:46Z","timestamp":1665490126000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Algorithms for Right-sizing Data Centers"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5848-5360","authenticated-orcid":false,"given":"Susanne","family":"Albers","sequence":"first","affiliation":[{"name":"Technical University of Munich, Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9690-0123","authenticated-orcid":false,"given":"Jens","family":"Quedenfeld","sequence":"additional","affiliation":[{"name":"Technical University of Munich, Garching, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465533"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49529-2_6"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.168"},{"key":"e_1_3_2_5_2","first-page":"164","volume-title":"Proceedings of the International Workshop on Approximation and Online Algorithms","author":"Antoniadis Antonios","year":"2017","unstructured":"Antonios Antoniadis and Kevin Schewior. 2017. A tight lower bound for online convex optimization with switching costs. In Proceedings of the International Workshop on Approximation and Online Algorithms. Springer, 164\u2013175."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.93"},{"key":"e_1_3_2_7_2","volume-title":"Above the Clouds: A Berkeley View of Cloud Computing","author":"Armbrust Michael","year":"2009","unstructured":"Michael Armbrust, Armando Fox, Rean Griffith, Anthony D. Joseph, Randy Katz, Andy Konwinski, Gunho Lee, David Patterson, Ariel Rabkin, Ion Stoica, and Matei Zaharia. 2009. Above the Clouds: A Berkeley View of Cloud Computing. Technical Report No. UCB\/EECS-2009-282. EECS Department, University of California, Berkeley."},{"key":"e_1_3_2_8_2","series-title":"LIPIcs","first-page":"96","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915)","author":"Bansal Nikhil","year":"2015","unstructured":"Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein. 2015. A 2-competitive algorithm for online convex optimization with switching costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915)(LIPIcs, Vol. 40). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 96\u2013109."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2007.443"},{"key":"e_1_3_2_10_2","unstructured":"Tom Bawden. 2016. Global warming: Data centres to consume three times as much energy in next decade experts warn. Retrieved from http:\/\/www.independent.co.uk\/environment\/global-warming-data-centres-to-consume-three-times-as-much-energy-in-next-decade-experts-warn-a6830086.html."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_3_2_12_2","article-title":"The invisible crisis in the data center: The economic meltdown of Moore\u2019s law","author":"Brill Kenneth G.","year":"2007","unstructured":"Kenneth G. Brill. 2007. The invisible crisis in the data center: The economic meltdown of Moore\u2019s law. White Pap., Uptime Instit.","journal-title":"White Pap., Uptime Instit."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1237879"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.91"},{"key":"e_1_3_2_15_2","first-page":"1574","article-title":"Smoothed online convex optimization in high dimensions via online balanced descent","volume":"75","author":"Chen Niangjun","year":"2018","unstructured":"Niangjun Chen, Gautam Goel, and Adam Wierman. 2018. Smoothed online convex optimization in high dimensions via online balanced descent. Proc. Mach. Learn. Res. 75 (2018), 1574\u20131594.","journal-title":"Proc. Mach. Learn. Res."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2015.2481183"},{"key":"e_1_3_2_17_2","unstructured":"Pierre Delforgeet al.2014. Data Center Efficiency Assessment. Retrieved from https:\/\/www.nrdc.org\/sites\/default\/files\/data-center-efficiency-assessment-IP.pdf."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120299"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2010.07.004"},{"key":"e_1_3_2_20_2","first-page":"2504","article-title":"An online algorithm for smoothed regression and LQR control","volume":"89","author":"Goel Gautam","year":"2019","unstructured":"Gautam Goel and Adam Wierman. 2019. An online algorithm for smoothed regression and LQR control. Proc. Mach. Learn. Res. 89 (2019), 2504\u20132513.","journal-title":"Proc. Mach. Learn. Res."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSDIS.2015.82"},{"key":"e_1_3_2_22_2","unstructured":"James Hamilton. 2008. Cost of Power in Large-Scale Data Centers. Retrieved from http:\/\/perspectives.mvdirona.com\/2008\/11\/cost-of-power-in-large-scale-data-centers\/."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.110"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.7"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2018.8431296"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5934885"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120298"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2308295"},{"key":"e_1_3_2_30_2","unstructured":"Patrick Schmid and Achim Roos. 2009. Overclocking Core i7: Power versus Performance. Retrieved from http:\/\/www.tomshardware.com\/reviews\/overclock-core-i7 2268-10.html."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.92"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.2172\/1372902"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.12.001"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2018.8619443"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565513","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3565513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:51Z","timestamp":1750182531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,16]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3565513"],"URL":"https:\/\/doi.org\/10.1145\/3565513","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2022,12,16]]},"assertion":[{"value":"2021-03-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}