A GRAPH-THEORETIC GAME, AND ITS APPLICATION TO THE K-SERVER PROBLEM

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)=O; 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, The main result is that the value of the game on any n-vertex graph is bounded above by exp(O(root log n log log n)). It is conjecrured 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 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 k.exp(O(root 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 cost (T, e) is less than or equal to exp(O(root 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.