A Graph-Theoretic Game and its Application to the k-Server Problem
Title | A Graph-Theoretic Game and its Application to the k-Server Problem |
Publication Type | Technical Report |
Year of Publication | 1991 |
Authors | Alon, N., Karp R. M., Peleg D., & West D. |
Other Numbers | 696 |
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 cost(T,e), defined as follows: If e lies in the tree T then cost(T,e)=0; if e does not lie in the tree then cost(T,e) = cycle(T,e)/w(e), where w(e) is the weight of edge e and cycle(T,e) is the weight of the unique cycle formed when edge e is added to the tree T. Our main result is that the value of the game on any n-vertex graph is bounded above by exp(O(sqrt{log n loglog 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). We show that, if the value of the game on G is Val(G,w), then there is a randomized strategy that achieves a competitive ratio of k(1 + 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 kcdotexp(O(sqrt{log n loglog n}))-competitive against oblivious adversaries.At the heart of our analysis of the game is an algorithm that, for any n-vertex weighted, connected multigraph, constructs a spanning tree T such that the average, over all edges e, of cost(T,e) is less than or equal to exp(O(sqrt{log n loglog n})). This result has potential application to the design of communication networks. [The on-line copy of this technical report was created from a later version (1992). A revised and expanded version of the paper appeared in the SIAM J. on Computing, Volume 24, (1995), pages 78-100.] |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1991/tr-91-066.pdf |
Bibliographic Notes | ICSI Technical Report TR-91-066 |
Abbreviated Authors | N. Alon, R. M. Karp, D. Peleg, and D. West |
ICSI Publication Type | Technical Report |