A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk R. Pruhs, Kevin Schewior, Clifford Stein · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
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.