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

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

doi:10.4230/LIPIcs.APPROX-RANDOM.2015.96

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

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

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

55 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 x_t 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 x_t. The cost paid by the online algorithm for this response is the distance moved, namely |x_t - x_t-1|, plus the value of the function at the final destination, namely Σ_t(x_t). The objective is then to minimize the aggregate cost over all time, namely Σ_t (|x_t - x_t-1| + f_t(x_t)). 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 language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
Editors	Naveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	96-109
Number of pages	14
ISBN (Electronic)	9783939897897
DOIs	https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.96
Publication status	Published - 1 Aug 2015
Event	18th 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 2015 → 26 Aug 2015

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	40
ISSN (Print)	1868-8969

Conference

Conference	18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
Country/Territory	United States
City	Princeton
Period	24/08/15 → 26/08/15

Bibliographical note

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

Funding

Supported by NWO grant 639.022.211 and an ERC consolidator grant 617951. Part of this work was done when the author was at Columbia University and supported by NSF grant CCF-1349602. Supported in part by NSF grants CCF-1115575, CNS-1253218, CCF-1421508, and an IBM Faculty Award. Supported by the Deutsche Forschungsgemeinschaft within the research training group "Methods for Discrete Structures" (GRK 1408). Supported in part by NSF grants CCF-1349602 and CCF-1421161.

Keywords

Scheduling
Stochastic

Access to Document

10.4230/LIPIcs.APPROX-RANDOM.2015.96

Cite this

Bansal, N., Gupta, A., Krishnaswamy, R., Pruhs, K., Schewior, K., & Stein, C. (2015). A 2-competitive algorithm for online convex optimization with switching costs. In N. Garg, K. Jansen, A. Rao, & J. D. P. Rolim (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015 (pp. 96-109). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 40). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.96

Bansal, Nikhil ; Gupta, Anupam ; Krishnaswamy, Ravishankar et al. / A 2-competitive algorithm for online convex optimization with switching costs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. editor / Naveen Garg ; Klaus Jansen ; Anup Rao ; Jose D. P. Rolim. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. pp. 96-109 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{8c1294b09eef42e79c992a594dc9dbfa,

title = "A 2-competitive algorithm for online convex optimization with switching costs",

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.",

keywords = "Scheduling, Stochastic",

author = "Nikhil Bansal and Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs and Kevin Schewior and Cliff Stein",

note = "Publisher Copyright: {\textcopyright} Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein.; 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 ; Conference date: 24-08-2015 Through 26-08-2015",

year = "2015",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.APPROX-RANDOM.2015.96",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "96--109",

editor = "Naveen Garg and Klaus Jansen and Anup Rao and Rolim, {Jose D. P.}",

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

}

Bansal, N, Gupta, A, Krishnaswamy, R, Pruhs, K, Schewior, K & Stein, C 2015, A 2-competitive algorithm for online convex optimization with switching costs. in N Garg, K Jansen, A Rao & JDP Rolim (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Leibniz International Proceedings in Informatics, LIPIcs, vol. 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 96-109, 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015, Princeton, United States, 24/08/15. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.96

A 2-competitive algorithm for online convex optimization with switching costs. / Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar et al.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. ed. / Naveen Garg; Klaus Jansen; Anup Rao; Jose D. P. Rolim. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. p. 96-109 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 40).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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

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 für Informatik

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 -

Bansal N, Gupta A, Krishnaswamy R, Pruhs K, Schewior K, Stein C. A 2-competitive algorithm for online convex optimization with switching costs. In Garg N, Jansen K, Rao A, Rolim JDP, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2015. p. 96-109. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.APPROX-RANDOM.2015.96

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

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this