Lower Bounds for Randomized k-Server and Motion-Planning Algorithms

DOI10.1137/S0097539792224838zbMath0804.68066OpenAlexW1981660486MaRDI QIDQ4291558

Yuval Rabani, Y. Ravid, Howard J. Karloff

Publication date: 10 May 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792224838

zbMATH Keywords

competitive analysison-line algorithmmotion planning\(k\)-server problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automated systems (robots, etc.) in control theory (93C85)

Related Items

Competitive randomized algorithms for nonuniform problems ⋮ Constructing competitive tours from local information ⋮ Competitive algorithms for the weighted server problem ⋮ Competitive distributed decision-making ⋮ A competitive analysis of nearest neighbor based algorithms for searching unknown scenes ⋮ Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ An introduction to the Ribe program ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ Low-distortion embeddings of infinite metric spaces into the real line ⋮ Competitive Algorithms for Layered Graph Traversal ⋮ A general decomposition theorem for the \(k\)-server problem