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

\(k\)-server algorithmscompetitive algorithm

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 432775 (Why is no real title available?)
• scientific article; zbMATH DE number 432777 (Why is no real title available?)
• New Ressults on Server Problems
• On fast algorithms for two servers

Cited in

(35)

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

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)