A Graph-Theoretic Game and Its Application to the k-Server Problem

DOI10.1137/S0097539792224474zbMath0818.90147WikidataQ106158661 ScholiaQ106158661MaRDI QIDQ4326854

Noga Alon, Douglas B. West, David Peleg, Richard M. Karp

Publication date: 3 July 1995

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

zbMATH Keywords

randomized algorithm; spanning tree; zero-sum game; road network; average stretch; \(k\)-server problems; simple network design; weighted connected graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

90C60: Abstract computational complexity for mathematical programming problems

91A43: Games involving graphs

68R10: Graph theory (including graph drawing) in computer science

90B06: Transportation, logistics and supply chain management

90B80: Discrete location and assignment

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Lower bounds for strictly fundamental cycle bases in grid graphs, A tight bound on approximating arbitrary metrics by tree metrics, A randomized algorithm for the on-line weighted bipartite matching problem, A network game with attackers and a defender, Minimum cut bases in undirected networks, Low-light trees, and tight lower bounds for Euclidean spanners, Random martingales and localization of maximal inequalities, Counting distance permutations, Edge-swapping algorithms for the minimum fundamental cycle basis problem, Minimum weakly fundamental cycle bases are hard to find, Randomized algorithm for the \(k\)-server problem on decomposable spaces, Minimum restricted diameter spanning trees., On approximating planar metrics by tree metrics., Low complexity variants of the arrow distributed directory, New length bounds for cycle bases, The zoo of tree spanner problems