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

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

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

• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive algorithms for server problems
• scientific article; zbMATH DE number 65695 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• 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

(28)

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

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)