A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems

DOI10.1137/S0097539799351882zbMath0977.68039MaRDI QIDQ2706128

Yuval Rabani, Avrim L. Blum, Michael E. Saks, Howard J. Karloff

Publication date: 19 March 2001

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

zbMATH Keywords

competitive analysislower boundson-line algorithmsrandomized algorithms\(k\)-servertask systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Combinatorial games (91A46)

Related Items

The weighted 2-server problem ⋮ On multi-threaded metrical task systems ⋮ Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem ⋮ An introduction to the Ribe program ⋮ Ultrametric subsets with large Hausdorff dimension ⋮ Parametrized Metrical Task Systems ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ Unified Algorithms for Online Learning and Competitive Analysis ⋮ Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing ⋮ A general decomposition theorem for the \(k\)-server problem

This page was built for publication: A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems