Competitive k-server algorithms

DOI10.1016/S0022-0000(05)80060-1zbMATH Open0806.68056OpenAlexW2157650361MaRDI QIDQ1329151FDOQ1329151

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)

Cites Work

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

Cited In (29)

• Title not available (Why is that?)
• Competitive clustering of stochastic communication patterns on a ring
• 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
• Title not available (Why is that?)
• Metrical service systems with multiple servers
• Secretary and online matching problems with machine learned advice
• Multi-Finger Binary Search Trees
• Competitive randomized algorithms for nonuniform problems
• A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem
• On the competitiveness of the move-to-front rule
• Title not available (Why is that?)
• Server problems and resistive spaces
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• The Canadian Traveller Problem and its competitive analysis
• Online \(k\)-taxi via double coverage and time-reverse primal-dual
• A competitive 2-server algorithm
• 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
• The \(K\)-server problem via a modern optimization lens
• Randomized competitive analysis for two server problems
• Competitive algorithms for the weighted server problem
• Lower bounds for searching robots, some faulty
• Competitive analysis of on-line disk scheduling

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Competitive algorithms for server problems 👍 👎
• On the competitive ratio of the work function algorithm for the \(k\)-server problem 👍 👎
• A competitive 2-server algorithm 👍 👎
• Competitive algorithms for the bicriteria \(k\)-server problem 👍 👎
• A Polylogarithmic-Competitive Algorithm for the k -Server Problem 👍 👎
• Competitive Algorithms for Generalized k -Server in Uniform Metrics 👍 👎

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)