Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
From MaRDI portal
Publication:4291558
DOI10.1137/S0097539792224838zbMath0804.68066MaRDI QIDQ4291558
Yuval Rabani, Y. Ravid, Howard J. Karloff
Publication date: 10 May 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
93C85: Automated systems (robots, etc.) in control theory
Related Items
Low-distortion embeddings of infinite metric spaces into the real line, Competitive randomized algorithms for nonuniform problems, Constructing competitive tours from local information, Competitive algorithms for the weighted server problem, A general decomposition theorem for the \(k\)-server problem, Competitive distributed decision-making, Ramsey-type theorems for metric spaces with applications to online problems, Competitive Algorithms for Layered Graph Traversal