The 3-server problem in the plane.

DOI10.1016/S0304-3975(01)00305-XMaRDI QIDQ1853532zbMATH OpenOpenAlexFDO

Authors Wolfgang W. Bein, Marek Chrobak, Lawrence L. Larmore

Publication date 21 January 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(01)00305-x

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)

Recommendations

• On the k -server conjecture
• scientific article; zbMATH DE number 1500547
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• On the competitive ratio of the work function algorithm for the k-server problem

Cites work

• scientific article; zbMATH DE number 65695 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive algorithms for server problems
• New Ressults on Server Problems
• On the k -server conjecture
• On the \(k\)-server conjecture
• Page Migration Algorithms Using Work Functions
• The 2-evader problem
• Traversing Layered Graphs Using the Work Function Algorithm

Cited in

(25)

• Competitive algorithms for the bicriteria \(k\)-server problem
• An application of various algorithms for solving the \(k\)-server problem
• A New Approach to the Server Problem
• Online k-server routing problems
• Generosity Helps or an 11-Competitive Algorithm for Three Servers
• Online chasing problems for regular polygons
• Manhattan orbifolds
• The online \(k\)-server problem with rejection
• Asymptotically optimal online page migration on three points
• On advice complexity of the \(k\)-server problem under sparse metrics
• A fast work function algorithm for solving the k-server problem
• Breaking the 2-competitiveness barrier for two servers in a tree
• The \(k\)-server problem
• Metrical service systems with multiple servers
• R-LINE: a better randomized 2-server algorithm on the line
• A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle
• Deterministic 3-server on a circle and the limitation of canonical potentials
• Online search for a hyperplane in high-dimensional Euclidean space
• A new upper bound on the work function algorithm for the \(k\)-server problem
• Online facility assignment
• On the competitive ratio of the work function algorithm for the k-server problem
• On the advice complexity of the \(k\)-server problem under sparse metrics
• The online \(k\)-server problem with max-distance objective
• A \(k\)-server problem with parallel requests and unit distances
• Online k-Server Routing Problems

This page was built for publication: The 3-server problem in the plane.

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