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

DOI10.1007/s10100-014-0349-4zbMath1339.90289OpenAlexW1976010297MaRDI QIDQ301952

Tomislav Rudec, Robert Manger

Publication date: 4 July 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-014-0349-4

zbMATH Keywords

combinatorial optimizationnetwork flowsimplementationon-line computation\(k\)-server problemwork function algorithmcost reduction

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

The work function algorithm for the paging problem, Editorial, A new upper bound on the work function algorithm for the \(k\)-server problem, Managing multiple mobile resources, Methodologies and applications for resilient global development from the aspect of SDI-SOR special issues of CJOR

Cites Work

• Unnamed Item
• A fast 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
• The \(k\)-server problem
• Online computation with advice
• On the additive constant of the \(k\)-server work function algorithm
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• Graphs, networks and algorithms. Based on the translation of the 3rd German edition by Tilla Schade in collaboration with the author
• On the k-server conjecture
• On the bicriteria k -server problem
• New Ressults on Server Problems
• Competitive algorithms for server problems