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

DOI10.1007/S10100-011-0222-7MaRDI QIDQ300972zbMATH OpenOpenAlexFDO

Authors Tomislav Rudec, Alfonzo Baumgartner, Robert Manger

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

\(k\)-server problemimplementationnetwork flowsonline algorithmsonline problemswork function algorithm

Mathematics Subject Classification ID

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

Recommendations

• A fast approximate implementation of the work function algorithm for solving the k-server problem
• The design and analysis of a modified work function algorithm for solving the on-line \(k\)-server problem
• A new approach to solve the k-server problem based on network flows and flow cost reduction
• A new upper bound on the work function algorithm for the k-server problem
• scientific article; zbMATH DE number 1500547

Cites work

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

Cited in

(15)

• The K-server problem via a modern optimization lens
• The fast algorithm for online \(k\)-server problem on trees
• The work function algorithm for the paging problem
• A new upper bound on the work function algorithm for the k-server problem
• Stochastic dominance and the bijective ratio of online algorithms
• An application of various algorithms for solving the k-server problem
• The design and analysis of a modified work function algorithm for solving the on-line \(k\)-server problem
• A fast approximate implementation of the work function algorithm for solving the k-server problem
• A new approach to solve the k-server problem based on network flows and flow cost reduction
• A fast implementation of the optimal off-line algorithm for solving the k-server problem
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• Managing multiple mobile resources
• Online L(2,1)-coloring problem on paths with restricted size of memory
• Time efficient implementation for online k-server problem on trees
• Geometric bipartite matching based exact algorithms for server problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300972)