文章基本信息

标题：Spanning-Tree Games
本地全文：下载
作者：Dan Hefetz ; Orna Kupferman ; Amir Lellouche 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：117
页码：1-16
DOI：10.4230/LIPIcs.MFCS.2018.35
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We introduce and study a game variant of the classical spanning-tree problem. Our spanning-tree game is played between two players, min and max, who alternate turns in jointly constructing a spanning tree of a given connected weighted graph G. Starting with the empty graph, in each turn a player chooses an edge that does not close a cycle in the forest that has been generated so far and adds it to that forest. The game ends when the chosen edges form a spanning tree in G. The goal of min is to minimize the weight of the resulting spanning tree and the goal of max is to maximize it. A strategy for a player is a function that maps each forest in G to an edge that is not yet in the forest and does not close a cycle. We show that while in the classical setting a greedy approach is optimal, the game setting is more complicated: greedy strategies, namely ones that choose in each turn the lightest (min) or heaviest (max) legal edge, are not necessarily optimal, and calculating their values is NP-hard. We study the approximation ratio of greedy strategies. We show that while a greedy strategy for min guarantees nothing, the performance of a greedy strategy for max is satisfactory: it guarantees that the weight of the generated spanning tree is at least w(MST(G))/2, where w(MST(G)) is the weight of a maximum spanning tree in G, and its approximation ratio with respect to an optimal strategy for max is 1.5+1/w(MST(G)), assuming weights in [0,1]. We also show that these bounds are tight. Moreover, in a stochastic setting, where weights for the complete graph K_n are chosen at random from [0,1], the expected performance of greedy strategies is asymptotically optimal. Finally, we study some variants of the game and study an extension of our results to games on general matroids.
关键词：Algorithms; Games; Minimum/maximum spanning tree; Greedy algorithms