Document Open Access Logo

A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.96.pdf
  • Filesize: 499 kB
  • 14 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein. A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 96-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.96

Abstract

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.

Subject Classification

Keywords
  • Stochastic
  • Scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Lachlan L. H. Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman. A tale of two metrics: Simultaneous bounds on competitiveness and regret. In COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, pages 741-763, 2013. Google Scholar
  2. Nikhil Bansal, Niv Buchbinder, and Joseph Naor. Towards the randomized k-server conjecture: A primal-dual approach. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 40-55, 2010. Google Scholar
  3. Yair Bartal, Béla Bollobás, and Manor Mendel. Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst. Sci., 72(5):890-921, 2006. Google Scholar
  4. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phenomena. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC'03, pages 463-472, New York, NY, USA, 2003. ACM. Google Scholar
  5. Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, 1992. Google Scholar
  6. M. Chrobak, H. Karloff, T. Payne, and S. Vishwanathan. New results on server problems. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'90, pages 291-300, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics. Google Scholar
  7. Aaron Coté, Adam Meyerson, and Laura Poplawski. Randomized k-server on hierarchical binary trees. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC'08, pages 227-234, New York, NY, USA, 2008. ACM. Google Scholar
  8. Amos Fiat and Manor Mendel. Better algorithms for unfair metrical task systems and applications. SIAM J. Comput., 32(6):1403-1422, 2003. Google Scholar
  9. Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan S. Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6):542-571, 1994. Google Scholar
  10. Minghong Lin, Zhenhua Liu, Adam Wierman, and Lachlan L. H. Andrew. Online algorithms for geographical load balancing. In 2012 International Green Computing Conference, IGCC 2012, San Jose, CA, USA, June 4-8, 2012, pages 1-10, 2012. Google Scholar
  11. Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Online dynamic capacity provisioning in data centers. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton Park & Retreat Center, Monticello, IL, USA, 28-30 September, 2011, pages 1159-1163, 2011. Google Scholar
  12. Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic right-sizing for power-proportional data centers. IEEE/ACM Trans. Netw., 21(5):1378-1391, 2013. Google Scholar
  13. Minghong Lin, Adam Wierman, Alan Roytman, Adam Meyerson, and Lachlan L. H. Andrew. Online optimization with switching cost. SIGMETRICS Performance Evaluation Review, 40(3):98-100, 2012. Google Scholar
  14. Zhenhua Liu, Minghong Lin, Adam Wierman, Steven H. Low, and Lachlan L. H. Andrew. Greening geographical load balancing. In SIGMETRICS 2011, Proceedings of the 2011 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, San Jose, CA, USA, 07-11 June 2011 (Co-located with FCRC 2011), pages 233-244, 2011. Google Scholar
  15. Kai Wang, Minghong Lin, Florin Ciucu, Adam Wierman, and Chuang Lin. Characterizing the impact of the workload on the value of dynamic resizing in data centers. In Proceedings of the IEEE INFOCOM 2013, Turin, Italy, April 14-19, 2013, pages 515-519, 2013. Google Scholar
  16. Adam Wierman. Personal communication, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact