Competitive \(k\)-server algorithms

DOI10.1016/S0022-0000(05)80060-1zbMath0806.68056OpenAlexW2157650361MaRDI QIDQ1329151

Y. Ravid, Amos Fiat, Yuval Rabani

Publication date: 29 June 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80060-1

zbMATH Keywords

competitive algorithm\(k\)-server algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (22)

Competitive randomized algorithms for nonuniform problems ⋮ A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle ⋮ Competitive algorithms for the weighted server problem ⋮ On the competitive ratio of the work function algorithm for the \(k\)-server problem ⋮ The CNN problem and other \(k\)-server variants ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ Secretary and online matching problems with machine learned advice ⋮ The \(k\)-server problem ⋮ Competitive clustering of stochastic communication patterns on a ring ⋮ Lower bounds for searching robots, some faulty ⋮ On convex body chasing ⋮ Metrical service systems with multiple servers ⋮ Dynamic location problems with limited look-ahead ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Server problems and resistive spaces ⋮ Multi-Finger Binary Search Trees ⋮ The Canadian Traveller Problem and its competitive analysis ⋮ On the competitiveness of the move-to-front rule ⋮ A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem ⋮ On the power of randomization in on-line algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• A strongly competitive randomized paging algorithm
• Competitive snoopy caching
• A competitive 2-server algorithm
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• On fast algorithms for two servers
• Competitive paging algorithms

This page was built for publication: Competitive \(k\)-server algorithms