Towards the randomized k-server conjecture, a primal-dual approach

MaRDI QIDQ5417604zbMATH OpenFDO

Authors N. Bansal, Niv Buchbinder, Joseph (Seffi) Naor

Publication date 22 May 2014

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Metrical task systems and the k-server problem on HSTs
• A primal-dual online algorithm for the k-server problem on weighted HSTs
• A polylogarithmic-competitive algorithm for the k-server problem
• \(k\)-server via multiscale entropic regularization
• On the k -server conjecture

Cited in

(10)

• A primal-dual online algorithm for the k-server problem on weighted HSTs
• The CNN problem and other k-server variants
• Online file caching with rejection penalties
• Unified algorithms for online learning and competitive analysis
• On variants of file caching
• Randomized k-server algorithms for growth-rate bounded graphs
• Metrical task systems and the k-server problem on HSTs
• scientific article; zbMATH DE number 6469207 (Why is no real title available?)
• A randomized algorithm for two servers in cross polytope spaces
• Online metric allocation and time-varying regularization

This page was built for publication: Towards the randomized \(k\)-server conjecture, a primal-dual approach

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