TY - GEN

T1 - Sorting noisy data with partial information

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Vijayaraghavan, Aravindan

PY - 2013/2/11

Y1 - 2013/2/11

N2 - 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.

AB - 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.

KW - approximation algorithm

KW - average-case analysis

KW - minimum feedback arc set

KW - semi-random model

UR - http://www.scopus.com/inward/record.url?scp=84873357200&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873357200&partnerID=8YFLogxK

U2 - 10.1145/2422436.2422492

DO - 10.1145/2422436.2422492

M3 - Conference contribution

AN - SCOPUS:84873357200

SN - 9781450318594

T3 - ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

SP - 515

EP - 528

BT - ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

T2 - 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013

Y2 - 9 January 2013 through 12 January 2013

ER -