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

DOI10.4230/LIPICS.APPROX-RANDOM.2015.96MaRDI QIDQ5351892zbMATH OpenOpenAlexFDO

Authors N. Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kevin Schewior, Kirk Pruhs, Clifford Stein

Publication date 31 August 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2015/5297/pdf/7.pdf/

zbMATH Keywords

schedulingstochastic

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27) Convex programming (90C25)

Recommendations

• A tight lower bound for online convex optimization with switching costs
• The optimal dynamic regret for smoothed online convex optimization with squared \(l_2\) norm switching costs
• Chasing convex bodies and functions
• Nearly Optimal Competitive Online Replacement Policies
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem

Cited in

(11)

• A tight lower bound for online convex optimization with switching costs
• Nested convex bodies are chaseable
• Online multistage subset maximization problems
• Handling critical jobs online: deadline scheduling and convex-body chasing
• scientific article; zbMATH DE number 7525448 (Why is no real title available?)
• Better Bounds for Online Line Chasing
• Algorithms for energy conservation in heterogeneous data centers
• Algorithms for energy conservation in heterogeneous data centers
• The optimal dynamic regret for smoothed online convex optimization with squared \(l_2\) norm switching costs
• Online multi-dimensional generalized assignment problem with predictions
• A generalized matching reconfiguration problem

This page was built for publication: A 2-competitive algorithm for online convex optimization with switching costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351892)