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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 (US)
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 fur Informatik GmbH, Dagstuhl Publishing
Pages	96-109
Number of pages	14
ISBN (Electronic)	9783939897897
DOIs	https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.96
State	Published - Aug 1 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: Aug 24 2015 → Aug 26 2015

Publication series

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

Other

Other	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	8/24/15 → 8/26/15

Keywords

Scheduling
Stochastic

ASJC Scopus subject areas

Software

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 fur Informatik GmbH, Dagstuhl Publishing. 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 fur Informatik GmbH, Dagstuhl Publishing, 2015. p. 96-109 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 40).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 fur Informatik GmbH, Dagstuhl Publishing, 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, 8/24/15. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.96

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 fur Informatik GmbH, Dagstuhl Publishing. 2015. p. 96-109. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 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 fur Informatik GmbH, Dagstuhl Publishing, 2015. pp. 96-109 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{3c58c01b8bdf430eb8a5bc399dc54e94,

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 (US)",

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

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

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

}

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 -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this