On the competitive ratio of the work function algorithm for the \(k\)-server problem

DOI10.1016/j.tcs.2004.06.001zbMath1072.68014MaRDI 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

zbMATH Keywords

Online algorithms; The \(k\)-server problem; Work function

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Online facility assignment, Managing multiple mobile resources, 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 \(k\)-server problem, On the advice complexity of the \(k\)-server problem under sparse metrics, A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs, Tight bounds for double coverage against weak adversaries, Nested convex bodies are chaseable, Reallocating multiple facilities on the line, A new upper bound on the work function algorithm for the \(k\)-server problem, 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

• Unnamed Item
• Unnamed Item
• Competitive \(k\)-server algorithms
• The 2-evader problem
• The 3-server problem in the plane.
• On the k-server conjecture
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• On the k -server conjecture
• The harmonic k -server algorithm is competitive