On the competitive ratio of the work function algorithm for the \(k\)-server problem
From MaRDI portal
Publication:1887093
DOI10.1016/J.TCS.2004.06.001zbMath1072.68014OpenAlexW2002247760MaRDI QIDQ1887093
Elias Koutsoupias, Yair Bartal
Publication date: 23 November 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.001
Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (17)
A fast work function algorithm for solving the \(k\)-server problem ⋮ A fast approximate implementation of the work function algorithm for solving the \(k\)-server problem ⋮ The work function algorithm for the paging problem ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ The \(k\)-server problem ⋮ Reallocating multiple facilities on the line ⋮ Dynamic pricing of servers on trees ⋮ Tight bounds for double coverage against weak adversaries ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Nested convex bodies are chaseable ⋮ Online facility assignment ⋮ A new upper bound on the work function algorithm for the \(k\)-server problem ⋮ Managing multiple mobile resources ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ The online \(k\)-server problem with rejection ⋮ The online \(k\)-server problem with max-distance objective ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics
Cites Work
This page was built for publication: On the competitive ratio of the work function algorithm for the \(k\)-server problem
