Competitive k-server algorithms

DOI10.1016/S0022-0000(05)80060-1MaRDI QIDQ1329151zbMATH OpenOpenAlexFDO

Authors Amos Fiat, Yuval Rabani, Y. Ravid

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)

Recommendations

• Competitive algorithms for server problems
• Competitive algorithms for the bicriteria \(k\)-server problem
• Competitive algorithms for generalized \(k\)-server in uniform metrics
• Competitive Algorithms for Generalized k -Server in Uniform Metrics
• A polylogarithmic-competitive algorithm for the \(k\)-server problem
• A competitive 2-server algorithm
• scientific article; zbMATH DE number 2038743
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• scientific article; zbMATH DE number 1500547

Cites work

• scientific article; zbMATH DE number 432775 (Why is no real title available?)
• scientific article; zbMATH DE number 432777 (Why is no real title available?)
• A competitive 2-server algorithm
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• A strongly competitive randomized paging algorithm
• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive paging algorithms
• Competitive snoopy caching
• New Ressults on Server Problems
• On fast algorithms for two servers

Cited in

(32)

• scientific article; zbMATH DE number 2038743 (Why is no real title available?)
• On convex body chasing
• scientific article; zbMATH DE number 65696 (Why is no real title available?)
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• Metrical service systems with multiple servers
• The \(K\)-server problem via a modern optimization lens
• Server problems and resistive spaces
• Competitive randomized algorithms for nonuniform problems
• Multi-Finger Binary Search Trees
• Online \(k\)-taxi via double coverage and time-reverse primal-dual
• A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem
• Lower bounds for searching robots, some faulty
• On the competitiveness of the move-to-front rule
• scientific article; zbMATH DE number 742965 (Why is no real title available?)
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs
• Secretary and online matching problems with machine learned advice
• The Canadian Traveller Problem and its competitive analysis
• The CNN problem and other \(k\)-server variants
• Randomized competitive analysis for two server problems
• Competitive algorithms for the weighted server problem
• Online Metric Algorithms with Untrusted Predictions
• The \(k\)-server problem
• Competitive algorithms for generalized \(k\)-server in uniform metrics
• Dynamic location problems with limited look-ahead
• A polylogarithmic-competitive algorithm for the \(k\)-server problem
• Competitive clustering of stochastic communication patterns on a ring
• A competitive 2-server algorithm
• Competitive analysis of on-line disk scheduling
• On the power of randomization in on-line algorithms
• The online \(k\)-server problem with max-distance objective
• Online \(k\)-taxi via double coverage and time-reverse primal-dual

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

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