Loading...
Please wait, while we are loading the content...
Similar Documents
Sorting Noisy Data with Partial Information
| Content Provider | CiteSeerX |
|---|---|
| Author | Makarychev, Konstantin Makarychev, Yury |
| Abstract | In this paper, we propose two semi-random models for the Minimum Feedback Arc Set Problem and present approxi-mation 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 so-lution of cost (1 + δ) opt-cost+npolylog n, where opt-cost is the cost of the optimal solution. For the second model, we give an approximation algorithm that finds a solution of cost O(planted-cost)+npolylog n, where planted-cost is the cost of the planted solution. Additionally, we present an approximation algorithm for semi-random instances of Minimum Directed Balanced Cut. |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |
