{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:38Z","timestamp":1750219958605,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T00:00:00Z","timestamp":1702512000000},"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":[[2023,12,31]]},"abstract":"<jats:p>\n            Power consumption is a dominant and still growing cost factor in data centers. In time periods with low load, the energy consumption can be reduced by powering down unused servers. We resort to a model introduced by Lin, Wierman, Andrew, and Thereska [\n            <jats:xref ref-type=\"bibr\">23<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">24<\/jats:xref>\n            ] that considers data centers with identical machines and generalize it to heterogeneous data centers with\n            <jats:italic>d<\/jats:italic>\n            different server types. The operating cost of a server depends on its load and is modeled by an increasing, convex function for each server type. In contrast to earlier work, we consider the discrete setting, where the number of active servers must be integral. Thereby, we seek truly feasible solutions. For homogeneous data centers (\n            <jats:italic>d<\/jats:italic>\n            =1), both the offline and the online problem were solved optimally in References [\n            <jats:xref ref-type=\"bibr\">3<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">4<\/jats:xref>\n            ].\n          <\/jats:p>\n          <jats:p>\n            In this article, we study heterogeneous data centers with general time-dependent operating cost functions. We develop an online algorithm based on a work function approach that achieves a competitive ratio of 2\n            <jats:italic>d<\/jats:italic>\n            + 1 + \u03b5 for any \u03b5 &gt; 0. For time-independent operating cost functions, the competitive ratio can be reduced to 2\n            <jats:italic>d<\/jats:italic>\n            + 1. There is a lower bound of\n            <jats:italic>2d<\/jats:italic>\n            shown in Reference\u00a0[\n            <jats:xref ref-type=\"bibr\">5<\/jats:xref>\n            ], so our algorithm is nearly optimal. For the offline version, we give a graph-based (1+\u03b5)-approximation algorithm. Additionally, our offline algorithm is able to handle time-variable data-center sizes.\n          <\/jats:p>","DOI":"10.1145\/3595286","type":"journal-article","created":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T12:24:53Z","timestamp":1683721493000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for Right-sizing Heterogeneous Data Centers"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5848-5360","authenticated-orcid":false,"given":"Susanne","family":"Albers","sequence":"first","affiliation":[{"name":"Technical University of Munich, 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, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087560"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3364210"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210385"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","unstructured":"Susanne Albers and Jens Quedenfeld. 2018. Optimal algorithms for right-sizing data centers\u2014Extended version. arxiv:cs.DS\/1807.05112.","DOI":"10.1145\/3210377.3210385"},{"key":"e_1_3_3_6_2","volume-title":"Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC\u201921)","author":"Albers Susanne","year":"2021","unstructured":"Susanne Albers and Jens Quedenfeld. 2021. Algorithms for energy conservation in heterogeneous data centers. In Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC\u201921). Springer, 75\u201389."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811044"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49529-2_6"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.168"},{"key":"e_1_3_3_10_2","first-page":"164","volume-title":"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 International Workshop on Approximation and Online Algorithms. Springer, 164\u2013175."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.93"},{"key":"e_1_3_3_12_2","first-page":"6730","volume-title":"Proceedings of the 54th IEEE Conference on Decision and Control (CDC\u201915)","author":"Badiei Masoud","year":"2015","unstructured":"Masoud Badiei, Na Li, and Adam Wierman. 2015. Online convex optimization with ramp constraints. In Proceedings of the 54th IEEE Conference on Decision and Control (CDC\u201915). IEEE, 6730\u20136736."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00661-x"},{"key":"e_1_3_3_14_2","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_3_15_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_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.91"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745854"},{"key":"e_1_3_3_18_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_3_19_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_3_20_2","first-page":"1291","volume-title":"Proceedings of the IEEE 56th Annual Conference on Decision and Control (CDC\u201917)","author":"Goel Gautam","year":"2017","unstructured":"Gautam Goel, Niangjun Chen, and Adam Wierman. 2017. Thinking fast and slow: Optimization decomposition across timescales. In Proceedings of the IEEE 56th Annual Conference on Decision and Control (CDC\u201917). IEEE, 1291\u20131298."},{"key":"e_1_3_3_21_2","unstructured":"Gautam Goel and Adam Wierman. 2019. An online algorithm for smoothed regression and LQR control. In The 22nd International Conference on Artificial Intelligence and Statistics AISTATS (Proceedings of Machine Learning Research) Vol. 89. PMLR 2504\u20132513."},{"key":"e_1_3_3_22_2","first-page":"1","volume-title":"Proceedings of the IEEE PES Innovative Smart Grid Technologies Conference (ISGT\u201914)","author":"Kim Seung-Jun","year":"2014","unstructured":"Seung-Jun Kim and Geogios B. Giannakis. 2014. Real-time electricity pricing for demand response using online convex optimization. In Proceedings of the IEEE PES Innovative Smart Grid Technologies Conference (ISGT\u201914). IEEE, 1\u20135."},{"key":"e_1_3_3_23_2","first-page":"1","volume-title":"Proceedings of the International Green Computing Conference (IGCC\u201912)","author":"Lin Minghong","year":"2012","unstructured":"Minghong Lin, Zhenhua Liu, Adam Wierman, and Lachlan L. H. Andrew. 2012. Online algorithms for geographical load balancing. In Proceedings of the International Green Computing Conference (IGCC\u201912). IEEE, 1\u201310."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_3_3_25_2","unstructured":"Minghong Lin Adam Wierman Lachlan L. H. Andrew and Eno Thereska. 2013. Dynamic right-sizing for power-proportional data centers\u2014Extended Version. (2013)."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3379484"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993744.1993767"},{"key":"e_1_3_3_28_2","volume-title":"Power Management Techniques for Data Centers: A Survey","author":"Mittal Sparsh","year":"2014","unstructured":"Sparsh Mittal. 2014. Power Management Techniques for Data Centers: A Survey. Technical report. Future Technologies Group, Oak Ridge National Laboratory."},{"key":"e_1_3_3_29_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.html."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.92"},{"issue":"142","key":"e_1_3_3_31_2","first-page":"7","article-title":"Heterogeneous processing: A strategy for augmenting moore\u2019s law","volume":"2006","author":"Shan Amar","year":"2006","unstructured":"Amar Shan. 2006. Heterogeneous processing: A strategy for augmenting moore\u2019s law. Linux J. 2006, 142 (2006), 7.","journal-title":"Linux J."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2567529.2567556"},{"key":"e_1_3_3_33_2","first-page":"2007","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201909)","author":"Wierman Adam","year":"2009","unstructured":"Adam Wierman, Lachlan L. H. Andrew, and Ao Tang. 2009. Power-aware speed scaling in processor sharing systems. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201909). IEEE, 2007\u20132015."},{"key":"e_1_3_3_34_2","first-page":"6025","volume-title":"Proceedings of the IEEE Conference on Decision and Control (CDC\u201918)","author":"Zhang Ming","year":"2018","unstructured":"Ming Zhang, Zizhan Zheng, and Ness B. Shroff. 2018. An online algorithm for power-proportional data centers with switching cost. In Proceedings of the IEEE Conference on Decision and Control (CDC\u201918). IEEE, 6025\u20136032."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3595286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3595286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:08Z","timestamp":1750182548000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3595286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,14]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3595286"],"URL":"https:\/\/doi.org\/10.1145\/3595286","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2023,12,14]]},"assertion":[{"value":"2021-11-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}