On a Cut-Matching Game for the Sparsest Cut Problem
On a Cut-Matching Game for the Sparsest Cut Problem
复制标题
关于最稀疏割问题的割匹配博弈
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
R. Khandekar;Subhash Khot;L. Orecchia;Nisheeth K. Vishnoi
我们研究了一个"被切"的参与人C和一个"匹配"的参与人M之间的博弈。这个游戏从一个n个顶点的空图G开始。在每一轮中，被切割的玩家选择顶点的二等分（S，S），并且匹配的玩家然后将S和S之间的完美匹配M（不一定属于G）添加到（多）图G。每一轮中玩家的选择可能取决于前几轮中的选择。当G成为边扩展器时，博弈结束。这个博弈的值，用瓦尔（n，C，M）表示，是博弈结束前的总回合数。我们研究这个博弈与无向图中的稀疏割问题的联系：如果存在多项式时间的割参与者Cf使得对所有M都有瓦尔（n，Cf，M）≤ f（n），则存在多项式时间的O（f（n））-近似算法来求解稀疏割问题.我们证明了不存在被切割的局中人C，即使是无限时间的局中人C，也不能保证所有匹配局中人M的瓦尔（n，C，M）= o（gap（n）），其中gap（n）是稀疏切割问题中三角不等式约束下的SDP的完整性间隙.回想一下gap（n）= Ω（log log n）[5]。因此，我们证明这种方法无法为该问题产生o（√ gap（n））-近似（特别是o（√ log log n）-近似）算法。此外，我们还证明了存在一个（超多项式时间）割参与人C，使得对于所有M，我们有瓦尔（n，C，M）= O（log n）。
We study the following game between a “cut” player C and a “matching” player M. The game starts with an empty graph G on n vertices. In each round, the cut player chooses a bisection (S, S) of vertices and the matching player then adds a perfect matching M (not necessarily belonging to G) between S and S to the (multi-)graph G. The choices of the players in each round may depend on those in the previous rounds. The game ends when G becomes an edge-expander. The value of this game, denoted by val(n, C,M), is the total number of rounds in the game before it ends. We study this game for its connection with the Sparsest Cut problem in undirected graphs: if there is a polynomial-time cut player Cf such that val(n, Cf ,M) ≤ f(n) for all M, then there is a polynomial-time O(f(n))-approximation algorithm for the Sparsest Cut problem. We show that there is no cut player C, even unbounded-time, that can ensure val(n, C,M) = o( √ gap(n)) for all matching players M, where gap(n) is the integrality gap of the well-studied SDP with triangle inequality constraints for the Sparsest Cut problem. Recall that gap(n) = Ω(log log n) [5]. Thus, we prove that this approach cannot yield a o( √ gap(n))-approximation (and in particular, o( √ log log n)-approximation) algorithm for this problem. Furthermore, we show that there is a (super-polynomial time) cut player C such that, for all M, we have val(n, C,M) = O(log n).