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

Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, Cliff Stein

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

51 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
EditorsNaveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages96-109
Number of pages14
ISBN (Electronic)9783939897897
DOIs
Publication statusPublished - 1 Aug 2015
Event18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 - Princeton, United States
Duration: 24 Aug 201526 Aug 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume40
ISSN (Print)1868-8969

Conference

Conference18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
Country/TerritoryUnited States
CityPrinceton
Period24/08/1526/08/15

Bibliographical note

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

Keywords

  • Scheduling
  • Stochastic

Fingerprint

Dive into the research topics of 'A 2-competitive algorithm for online convex optimization with switching costs'. Together they form a unique fingerprint.

Cite this