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

(33)

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

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)