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

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

zbMATH Keywords

Online algorithmsThe \(k\)-server problemWork function

Mathematics Subject Classification ID

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

• 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

This page was built for publication: On the competitive ratio of the work function algorithm for the \(k\)-server problem