2026-08-04T09:09:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5297 2024-03-06T10:36:15Z ddc:004 open_access

A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs Bansal, Nikhil Gupta, Anupam Krishnaswamy, Ravishankar Pruhs, Kirk Schewior, Kevin Stein, Cliff Stochastic Scheduling We consider a natural online optimization problem set on the real line. The state of the online algorithm at each integer time is a location on the real line. At each integer time, a convex function arrives online. In response, the online algorithm picks a new location. The cost paid by the online algorithm for this response is the distance moved plus the value of the function at the final destination. The objective is then to minimize the aggregate cost over all time. The motivating application is rightsizing power-proportional data centers. We give a 2-competitive algorithm for this problem. We also give a 3-competitive memoryless algorithm, and show that this is the best competitive ratio achievable by a deterministic memoryless algorithm. Finally we show that this online problem is strictly harder than the standard ski rental problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Bansal and Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs and Kevin Schewior and Cliff Stein 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.96 urn:nbn:de:0030-drops-52970 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.96 eng https://creativecommons.org/licenses/by/3.0/legalcode