Metrical task systems on trees via mirror descent and unfair gluing

DOI10.1137/19M1237879MaRDI QIDQ4994985zbMATH OpenFDO

Authors Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee

Publication date 22 June 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1137/19M1237879

zbMATH Keywords

convex optimizationfinite metric spaceonline algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Recommendations

• Metrical task systems on trees via mirror descent and unfair gluing
• scientific article; zbMATH DE number 1559591
• scientific article; zbMATH DE number 910899
• Metrical task systems and the k-server problem on HSTs
• Randomized algorithms for metrical task systems

Cites work

• \(k\)-server via multiscale entropic regularization
• A decomposition theorem for task systems and bounds for randomized server problems
• A first course in Sobolev spaces
• A polylogarithmic-competitive algorithm for the k-server problem
• A primal-dual randomized algorithm for weighted paging
• A tight bound on approximating arbitrary metrics by tree metrics
• An optimal on-line algorithm for metrical task system
• Better Algorithms for Unfair Metrical Task Systems and Applications
• scientific article; zbMATH DE number 1559591 (Why is no real title available?)
• Metrical task systems and the k-server problem on HSTs
• Ramsey-type theorems for metric spaces with applications to online problems
• Unfair problems and randomized algorithms for metrical task systems

Cited in

(5)

• Better algorithms for unfair metrical task systems and applications
• Metrical task systems and the k-server problem on HSTs
• Better Algorithms for Unfair Metrical Task Systems and Applications
• Metrical task systems on trees via mirror descent and unfair gluing
• Smoothed analysis of online metric problems

This page was built for publication: Metrical task systems on trees via mirror descent and unfair gluing

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