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

DOI10.1137/S0097539792224474zbMath0818.90147OpenAlexW1981859328WikidataQ106158661 ScholiaQ106158661MaRDI QIDQ4326854

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

Publication date: 3 July 1995

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

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

zbMATH Keywords

randomized algorithmspanning treezero-sum gameroad networkaverage stretch\(k\)-server problemssimple network designweighted connected graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Transportation, logistics and supply chain management (90B06) Discrete location and assignment (90B80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (51)

A randomized algorithm for the on-line weighted bipartite matching problem ⋮ New length bounds for cycle bases ⋮ Models and algorithms for network reduction ⋮ Covering metric spaces by few trees ⋮ Terminal embeddings ⋮ Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ Lossless Prioritized Embeddings ⋮ Stochastic approximation of lamplighter metrics ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Maximum gradient embeddings and monotone clustering ⋮ \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees ⋮ Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Minimum restricted diameter spanning trees. ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ The geometry of synchronization problems and learning group actions ⋮ A network game with attackers and a defender ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ The mixed Lipschitz space and its dual for tree metrics ⋮ The zoo of tree spanner problems ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Minimum cut bases in undirected networks ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Random martingales and localization of maximal inequalities ⋮ Lower bounds for strictly fundamental cycle bases in grid graphs ⋮ Unnamed Item ⋮ Approximating snowflake metrics by trees ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Counting distance permutations ⋮ Edge-swapping algorithms for the minimum fundamental cycle basis problem ⋮ Local embeddings of metric spaces ⋮ Connected subgraph defense games ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ Covering Metric Spaces by Few Trees ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ On minimum average stretch spanning trees in polygonal 2-trees ⋮ Electrical flows over spanning trees ⋮ Near-Optimal Distributed Maximum Flow ⋮ On approximating planar metrics by tree metrics. ⋮ Low complexity variants of the arrow distributed directory

This page was built for publication: A Graph-Theoretic Game and Its Application to the k-Server Problem