Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing

DOI10.1137/19M1237879MaRDI QIDQ4994985

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

Publication date: 22 June 2021

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

zbMATH Keywords

convex optimizationonline algorithmsfinite metric space

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unfair problems and randomized algorithms for metrical task systems
• Ramsey-type theorems for metric spaces with applications to online problems
• On metric Ramsey-type phenomena
• A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems
• A Polylogarithmic-Competitive Algorithm for the k -Server Problem
• Metrical Task Systems and the k-Server Problem on HSTs
• An optimal on-line algorithm for metrical task system
• Better Algorithms for Unfair Metrical Task Systems and Applications
• k-server via multiscale entropic regularization
• A Primal-Dual Randomized Algorithm for Weighted Paging
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing