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

DOI10.1007/S10100-011-0222-7MaRDI QIDQ300972zbMATHOpenAlexFDO

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

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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) 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)

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
• Publication:4501566

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

(14)

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

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)