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)

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