TY - GEN

T1 - A 2-competitive algorithm for online convex optimization with switching costs

AU - Bansal, Nikhil

AU - Gupta, Anupam

AU - Krishnaswamy, Ravishankar

AU - Pruhs, Kirk

AU - Schewior, Kevin

AU - Stein, Cliff

N1 - Publisher Copyright:
© Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein.

PY - 2015/8/1

Y1 - 2015/8/1

N2 - We consider a natural online optimization problem set on the real line. The state of the online algorithm at each integer time t is a location xt on the real line. At each integer time t, a convex function ft(x) arrives online. In response, the online algorithm picks a new location xt. The cost paid by the online algorithm for this response is the distance moved, namely |xt - xt-1|, plus the value of the function at the final destination, namely Σt(xt). The objective is then to minimize the aggregate cost over all time, namely Σt (|xt - xt-1| + ft(xt)). 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.

AB - We consider a natural online optimization problem set on the real line. The state of the online algorithm at each integer time t is a location xt on the real line. At each integer time t, a convex function ft(x) arrives online. In response, the online algorithm picks a new location xt. The cost paid by the online algorithm for this response is the distance moved, namely |xt - xt-1|, plus the value of the function at the final destination, namely Σt(xt). The objective is then to minimize the aggregate cost over all time, namely Σt (|xt - xt-1| + ft(xt)). 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.

KW - Scheduling

KW - Stochastic

UR - http://www.scopus.com/inward/record.url?scp=84958523405&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958523405&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2015.96

DO - 10.4230/LIPIcs.APPROX-RANDOM.2015.96

M3 - Conference contribution

AN - SCOPUS:84958523405

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 96

EP - 109

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015

A2 - Garg, Naveen

A2 - Jansen, Klaus

A2 - Rao, Anup

A2 - Rolim, Jose D. P.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015

Y2 - 24 August 2015 through 26 August 2015

ER -