A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract)
A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract)
复制标题
DOI：
10.1090/dimacs/007/01
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
N. Alon;R. Karp;D. Peleg;D. West
中科院分区：
文献类型：
--
作者：
N. Alon;R. Karp;D. Peleg;D. West
本文调查了两个玩家（树玩家和边缘播放器）之间在加权连接的Graph G上玩的零和游戏。在每场比赛中，树玩家都会选择一个跨越树T，而边缘玩家选择了一个边缘e。对边缘播放器的薪资是成本（t; e），如下所示：如果e位于树上，则成本（t; e）= 0;如果e不在树上，则成本（t; e）=循环（t; e）= w（e），其中w（e）是边缘E和周期的重量（t; e）是重量当将边缘E添加到树T中时形成的唯一循环。我们的主要结果是在N-Vertex图上的游戏值在上方由EXP（O（p log n log log n））界定。游戏与道路网络上的K-Server问题有关；即，可以表示为多编码G的度量空间，其中每个边缘代表长度为w（e）的道路。我们表明，如果游戏对G的价值是v al（g; w），那么就有一种随机策略可以实现K（1 + V al（g; w））与任何遗忘对手的竞争比。因此，在任何N-Vertex Road网络上，都有一个随机算法，即K-Server问题是K Exp（O（p log n log log n）） - 与遗忘的对手竞争。我们对游戏分析的核心是一种算法，对于任何n-vertex加权，连接的多编码，构造一个跨树t，使得在所有边缘E中的平均成本（t; e）都小于或小于或等于EXP（O（p log n log log n））。该结果可能在通信网络的设计中使用。
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 payoo to the edge player is cost(T ; e), deened 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 an n-vertex graph is bounded above by exp(O(p log n log 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). We show that, if the value of the game on G is V al(G; w), then there is a randomized strategy that achieves a competitive ratio of k(1 + V al(G; w)) against any oblivious adversary. Thus, on any n-vertex road network, there is a random-ized algorithm for the k-server problem that is k exp(O(p log n log log 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(p log n log log n)). This result has potential application to the design of communication networks.