Sorting noisy data with partial information
Sorting noisy data with partial information
复制标题
使用部分信息对噪声数据进行排序
DOI：
10.1145/2422436.2422492
复制
发表时间：
2013
期刊：
影响因子：
20.3
通讯作者：
Aravindan Vijayaraghavan
中科院分区：
文献类型：
--
作者：
K. Makarychev;Yury Makarychev;Aravindan Vijayaraghavan
在本文中，我们为最小反馈弧设置问题提出了两个半随机模型，并在第一个模型中呈现近似算法。任意的异步有向图，然后随机翻转其边缘（对手可能会在第二个模型中解开其中的一些）。使用任意的无环形图，但现在添加新的随机后退边缘（对手可以删除其中的一些模型）。 OPT是第二个模型的最佳解决方案的成本，我们提供了一种近似算法，该算法找到了成本O（种植） + N Polylog N的解决方案，在该算法中，种植是种植解决方案的成本。半随机实例的近似算法，最小对定向平衡切割。
In this paper, we propose two semi-random models for the Minimum Feedback Arc Set Problem and present approximation algorithms for them. In the first model, which we call the Random Edge Flipping model, an instance is generated as follows. We start with an arbitrary acyclic directed graph and then randomly flip its edges (the adversary may later un-flip some of them). In the second model, which we call the Random Backward Edge model, again we start with an arbitrary acyclic graph but now add new random backward edges (the adversary may delete some of them). For the first model, we give an approximation algorithm that finds a solution of cost (1+ δ) OPT + n polylog n, where OPT is the cost of the optimal solution. For the second model, we give an approximation algorithm that finds a solution of cost O(planted) + n polylog n, where planted is the cost of the planted solution. Additionally, we present an approximation algorithm for semi-random instances of Minimum Directed Balanced Cut.