A fast work function algorithm for solving the \(k\)-server problem

DOI10.1007/s10100-011-0222-7zbMath1339.68031OpenAlexW2113692056MaRDI QIDQ300972

Tomislav Rudec, Robert Manger, Alfonzo Baumgartner

Publication date: 29 June 2016

Published in: CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10100-011-0222-7

zbMATH Keywords

online algorithmsnetwork flowsimplementation\(k\)-server problemonline problemswork function algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Internet topics (68M11) Online algorithms; streaming algorithms (68W27)

Related Items (8)

A fast approximate implementation of the work function algorithm for solving the \(k\)-server problem ⋮ The work function algorithm for the paging problem ⋮ Online \(L(2,1)\)-coloring problem on paths with restricted size of memory ⋮ The \(K\)-server problem via a modern optimization lens ⋮ 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 fast algorithm for online \(k\)-server problem on trees

Cites Work

• Unnamed Item
• Unnamed Item
• The \(k\)-server problem
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• The 2-evader problem
• The 3-server problem in the plane.
• A randomized algorithm for two servers on the line.
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• New Ressults on Server Problems
• Competitive algorithms for server problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The harmonic k -server algorithm is competitive

This page was built for publication: A fast work function algorithm for solving the \(k\)-server problem