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

TitleA Graph-Theoretic Game and its Application to the k-Server Problem
Publication TypeTechnical Report
Year of Publication1991
AuthorsAlon, N., Karp R. M., Peleg D., & West D.
Other Numbers696

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.]

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