Generosity Helps or an 11-Competitive Algorithm for Three Servers

DOI10.1006/JAGM.1994.1011MaRDI QIDQ4285911zbMATH OpenOpenAlexFDO

Authors Lawrence L. Larmore, Marek Chrobak

Publication date 22 March 1994

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1994.1011

zbMATH Keywords

11-competitive algorithm\(k\)-server problemconvex hulls

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 742965
• The harmonic k -server algorithm is competitive
• A competitive 2-server algorithm
• The 3-server problem in the plane.
• On the k -server conjecture

Cited in

(25)

• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Manhattan orbifolds
• A T_X-approach to some results on cuts and metrics
• Competitive analysis of randomized paging algorithms
• The polytopal structure of the tight-span of a totally split-decomposable metric
• Searching for realizations of finite metric spaces in tight spans
• On tight spans for directed distances
• Metric packing for \(K_ 3 + K_ 3\)
• Injective subsets of \(l_{\infty}(I)\)
• Mini-workshop: Nonpositively curved complexes. Abstracts from the mini-workshop held February 7--13, 2021 (online meeting)
• Completeness in generalized ultrametric spaces
• Injective metrizability and the duality theory of cubings
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• On di-injective \(T_{0}\)-quasi-metric spaces
• Obtaining splits from cut sets of tight spans
• The tight span of an antipodal metric space. I: combinatorial properties
• Injective hulls of certain discrete metric spaces and groups.
• Trees, tight-spans and point configurations
• The \(k\)-server problem
• scientific article; zbMATH DE number 742965 (Why is no real title available?)
• STACS 2004
• Coarse injectivity, hierarchical hyperbolicity and semihyperbolicity
• Helly groups
• On the structure of the tight-span of a totally split-decomposable metric
• Some characterizations of ultrametrically injective spaces

This page was built for publication: Generosity Helps or an 11-Competitive Algorithm for Three Servers

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