Oblivious Algorithms for the Maximum Directed Cut Problem
Oblivious Algorithms for the Maximum Directed Cut Problem
复制标题
最大定向割问题的不经意算法
DOI：
10.1007/s00453-013-9806-z
复制
发表时间：
2010
期刊：
影响因子：
1.1
通讯作者：
Shlomo Jozeph
中科院分区：
文献类型：
--
作者：
U. Feige;Shlomo Jozeph
本文介绍了我们称为“遗忘算法”的Max Dicut的特殊随机算法系列。让顶点的偏见为其外边缘的总重量与所有边缘的总重量之间的比率。遗忘算法在切割的哪一侧随机选择以放置顶点V，其概率仅取决于V的偏置，而与其他顶点无关。读者可以观察到，忽略偏差并以概率为1/2选择的算法的近似值为1/4，而没有忽略的算法可以比1/2更好的近似值（均匀定向循环服务）作为负面的例子）。我们试图表征通过遗忘算法可以达到的最佳近似比，并提出几乎紧密的结果。本文还讨论了遗忘算法概念的自然扩展，并讨论了最大2和最一般问题的扩展。
This paper introduces a special family of randomized algorithms for Max DICUT that we call oblivious algorithms. Let the bias of a vertex be the ratio between the total weight of its outgoing edges and the total weight of all its edges. An oblivious algorithm selects at random in which side of the cut to place a vertex v, with probability that only depends on the bias of v, independently of other vertices. The reader may observe that the algorithm that ignores the bias and chooses each side with probability 1/2 has an approximation ratio of 1/4, whereas no oblivious algorithm can have an approximation ratio better than 1/2 (with an even directed cycle serving as a negative example). We attempt to characterize the best approximation ratio achievable by oblivious algorithms, and present results that are nearly tight. The paper also discusses natural extensions of the notion of oblivious algorithms, and extensions to the more general problem of Max 2-AND.