{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T22:23:13Z","timestamp":1785795793189,"version":"3.56.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T00:00:00Z","timestamp":1701907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1745301, CAREER-2045641, CNS-2102963, CNS-2106299, CNS-2146814, CNS-1518941, CPS-2136197, CPS-2136199, NGSDI-2105494, NGSDI-2105648, 1908298, 2020888, 2021693, 2045641, 2213636, and 2211888"],"award-info":[{"award-number":["DGE-1745301, CAREER-2045641, CNS-2102963, CNS-2106299, CNS-2146814, CNS-1518941, CPS-2136197, CPS-2136199, NGSDI-2105494, NGSDI-2105648, 1908298, 2020888, 2021693, 2045641, 2213636, and 2211888"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["Computational Science Graduate Fellowship"],"award-info":[{"award-number":["Computational Science Graduate Fellowship"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2023,12,7]]},"abstract":"<jats:p>We introduce and study the online pause and resume problem. In this problem, a player attempts to find the k lowest (alternatively, highest) prices in a sequence of fixed length T, which is revealed sequentially. At each time step, the player is presented with a price and decides whether to accept or reject it. The player incurs aswitching cost whenever their decision changes in consecutive time steps, i.e., whenever they pause or resume purchasing. This online problem is motivated by the goal of carbon-aware load shifting, where a workload may be paused during periods of high carbon intensity and resumed during periods of low carbon intensity and incurs a cost when saving or restoring its state. It has strong connections to existing problems studied in the literature on online optimization, though it introduces unique technical challenges that prevent the direct application of existing algorithms. Extending prior work on threshold-based algorithms, we introducedouble-threshold algorithms for both the minimization and maximization variants of this problem. We further show that the competitive ratios achieved by these algorithms are the best achievable by any deterministic online algorithm. Finally, we empirically validate our proposed algorithm through case studies on the application of carbon-aware load shifting using real carbon trace data and existing baseline algorithms.<\/jats:p>","DOI":"10.1145\/3626776","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T15:20:29Z","timestamp":1702394429000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7774-9939","authenticated-orcid":false,"given":"Adam","family":"Lechowicz","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8330-8964","authenticated-orcid":false,"given":"Nicolas","family":"Christianson","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9557-3551","authenticated-orcid":false,"given":"Jinhang","family":"Zuo","sequence":"additional","affiliation":[{"name":"California Institute of Technology &amp; University of Massachusetts Amherst, Pasadena, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9304-910X","authenticated-orcid":false,"given":"Noman","family":"Bashir","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9278-2254","authenticated-orcid":false,"given":"Mohammad","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-0199","authenticated-orcid":false,"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5435-1901","authenticated-orcid":false,"given":"Prashant","family":"Shenoy","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575754"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IC2E48712.2020.00018"},{"key":"e_1_2_1_3_1","volume-title":"Online Computation with Untrusted Advice. arxiv","author":"Angelopoulos Spyros","year":"1905","unstructured":"Spyros Angelopoulos, Christoph D\u00fcrr, Shendan Jin, Shahin Kamali, and Marc Renault. 2022. Online Computation with Untrusted Advice. arxiv: 1905.05655 [cs.DS]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3524971"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bjp.2013.12.009"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472883.3487009"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585132"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1237879"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.91"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 31st Conference On Learning Theory. PMLR, 1574--1594","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. In Proceedings of the 31st Conference On Learning Theory. PMLR, 1574--1594."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 35th Conference on Learning Theory","volume":"178","author":"Christianson Nicolas","year":"2022","unstructured":"Nicolas Christianson, Tinashe Handina, and Adam Wierman. 2022. Chasing Convex Bodies and Functions with Black-Box Advice. In Proceedings of the 35th Conference on Learning Theory, Vol. 178. PMLR, 867--908."},{"key":"e_1_2_1_13_1","volume-title":"International Conference on Artificial Intelligence and Statistics.","author":"Christianson Nicolas","year":"2023","unstructured":"Nicolas Christianson, Junxuan Shen, and Adam Wierman. 2023. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. In International Conference on Artificial Intelligence and Statistics."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007--9156--9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_16_1","unstructured":"National Center for Biotechnology Information. 2022. Basic Local Alignment Search Tool (BLAST). https:\/\/blast.ncbi.nlm.nih.gov."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf02189324"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2010.07.004"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307772.3328307"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604930.3605709"},{"key":"e_1_2_1_21_1","first-page":"51","article-title":"Inequalities on the Lambert W function and hyperpower function","volume":"9","author":"Hoorfar Abdolhossein","year":"2008","unstructured":"Abdolhossein Hoorfar and Mehdi Hassani. 2008. Inequalities on the Lambert W function and hyperpower function. Journal of Inequalities in Pure and Applied Mathematics, Vol. 9, 51 (Jan. 2008). Issue 2.","journal-title":"Journal of Inequalities in Pure and Applied Mathematics"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.2.310"},{"key":"e_1_2_1_23_1","unstructured":"Russell Lee Bo Sun John C. S. Lui and Mohammad Hajiesmaili. 2022. Pareto-Optimal Learning-Augmented Algorithms for Online k-Search Problems. arxiv: 2211.06567 https:\/\/arxiv.org\/abs\/2211.06567"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530894"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IGCC.2012.6322266"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254779"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2007116.2007139"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008--9217--8"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"3305","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvtiskii. 2018. Competitive Caching with Machine Learned Advice. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80), Jennifer Dy and Andreas Krause (Eds.). PMLR, 3296--3305. https:\/\/proceedings.mlr.press\/v80\/lykouris18a.html"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3538637.3538849"},{"key":"e_1_2_1_32_1","unstructured":"Electricity Maps. 2020. Electricity Map. https:\/\/www.electricitymap.org\/map."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-011-0932--1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sorms.2014.08.001"},{"key":"e_1_2_1_35_1","volume-title":"Garnett (Eds.)","volume":"31","author":"Purohit Manish","year":"2018","unstructured":"Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving Online Algorithms via ML Predictions. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc."},{"key":"e_1_2_1_36_1","volume-title":"Nick Care, et al","author":"Radovanovic Ana","year":"2022","unstructured":"Ana Radovanovic, Ross Koningstein, Ian Schneider, Bokan Chen, Alexandre Duarte, Binz Roy, Diyue Xiao, Maya Haridasan, Patrick Hung, Nick Care, et al. 2022. Carbon-Aware Computing for Datacenters. IEEE Transactions on Power Systems (2022)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476205"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Daan Rutten Nicolas Christianson Debankur Mukherjee and Adam Wierman. 2022. Smoothed Online Optimization with Unreliable Predictions. https:\/\/doi.org\/10.48550\/arXiv.2202.03519","DOI":"10.48550\/arXiv.2202.03519"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381181"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.84"},{"key":"e_1_2_1_41_1","unstructured":"Shaden Smith Mostofa Patwary Brandon Norick Patrick LeGresley Samyam Rajbhandari Jared Casper Zhun Liu Shrimai Prabhumoye George Zerveas Vijay Korthikanti et al. 2022. Using DeepSpeed and Megatron to Train Megatron-Turing NLG 530B a Large-Scale Generative Language Model. arXiv preprint arXiv:2201.11990 (2022)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575709"},{"key":"e_1_2_1_43_1","first-page":"96","article-title":"On Certain Inequalities Involving the Lambert W function","volume":"10","author":"Stewart Se\u00e1n M.","year":"2009","unstructured":"Se\u00e1n M. Stewart. 2009. On Certain Inequalities Involving the Lambert W function. Journal of Inequalities in Pure and Applied Mathematics, Vol. 10, 96 (Nov. 2009). Issue 4.","journal-title":"Journal of Inequalities in Pure and Applied Mathematics"},{"key":"e_1_2_1_44_1","volume-title":"Wortman Vaughan (Eds.)","volume":"34","author":"Sun Bo","year":"2021","unstructured":"Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. 2021. Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 10339--10350. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/55a988dfb00a914717b3000a3374694c-Paper.pdf"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570618"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428336"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 22nd International Middleware Conference. Association for Computing Machinery","author":"Wiesner Philipp","year":"2021","unstructured":"Philipp Wiesner, Ilja Behnke, Dominik Scheinert, Kordian Gontarska, and Lauritz Thamsen. 2021. Let's Wait A While: How Temporal Workload Shifting Can Reduce Carbon Emissions in the Cloud. In Proceedings of the 22nd International Middleware Conference. Association for Computing Machinery, New York, NY, USA, 260--272."},{"key":"e_1_2_1_48_1","volume-title":"SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models. In International Conference on Machine Learning (Proceedings of Machine Learning Research). PMLR, PMLR","author":"Xiao Guangxuan","year":"2023","unstructured":"Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. 2023. SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models. In International Conference on Machine Learning (Proceedings of Machine Learning Research). PMLR, PMLR, Honolulu, HI, USA, 38087--38099."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3379482"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3491042"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2011.6133628"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpowsour.2006.06.040"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084460"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--92185--1_63"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:13:58Z","timestamp":1755908038000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,7]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,12,7]]}},"alternative-id":["10.1145\/3626776"],"URL":"https:\/\/doi.org\/10.1145\/3626776","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,7]]},"assertion":[{"value":"2023-12-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}