A Graph-Theoretic Game and Its Application to the k-Server Problem
Authors:
- Noga AlonNANoga Alon
- Richard M. KarpRKRichard M. Karp
- David PelegDPDavid Peleg
- Douglas WestDWDouglas West
- 1 February 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 24 (1) , 78-100
Abstract
This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and the edge player chooses an edge e. The payoff to the edge player is $\textit{cost} (T, e)$, defined as follows: If e lies in the tree T then $\textit{cost}(T, e) = 0$; if e does not lie in the tree then $\textit{cost}(T, e) = cycle(T, e)/w(e)$, where $w(e)$ is the weight of edge e and $\textit{cycle}(T, e)$ is the weight of the unique cycle formed when edge e is added to the tree T. The main result is that the value of the game on any n-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log \log n}))$. It is conjectured that the value of the game is $O(\log n)$. The game arises in connection with the k-server problem on a road network; i.e., a metric space that can be represented as a multigraph G in which each edge e represents a road of length $w(e)$. It is shown that, if the value of the game on G is $\textit{Val}(G, w)$, then there is a randomized strategy that achieves a competitive ratio of $k(1 + \textit{Val}(G, w))$ against any oblivious adversary. Thus, on any n-vertex road network, there is a randomized algorithm for the k-server problem that is $k \cdot \exp(O(\sqrt{\log n \log \log n}))$ competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any n-vertex weighted, connected multigraph, the algorithm constructs a spanning tree T such that the average, over all edges e, of $\textit{cost}(T, e)$ is less than or equal to $\exp(O(\sqrt{\log n \log \log n}))$. This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph.
Keywords
This publication has 14 references indexed in Scilit:
- A deterministicO(k 3)-competitivek-server algorithm for the circleAlgorithmica, 1994
- An optimal on-line algorithm for metrical task systemJournal of the ACM, 1992
- Competitive paging algorithmsJournal of Algorithms, 1991
- An Optimal On-Line Algorithm for K Servers on TreesSIAM Journal on Computing, 1991
- Competitive algorithms for server problemsJournal of Algorithms, 1990
- Generating sparse spanners for weighted graphs1990
- Some intersection theorems for ordered sets and graphsJournal of Combinatorial Theory, Series A, 1986
- Complexity of network synchronizationJournal of the ACM, 1985
- The complexity of the network design problemNetworks, 1978
- Optimum Communication Spanning TreesSIAM Journal on Computing, 1974