Sorting noisy data with partial information

Konstantin Makarychev*, Yury Makarychev, Aravindan Vijayaraghavan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science
Pages515-528
Number of pages14
DOIs
StatePublished - Feb 11 2013
Event2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 - Berkeley, CA, United States
Duration: Jan 9 2013Jan 12 2013

Publication series

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

Other

Other2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013
CountryUnited States
CityBerkeley, CA
Period1/9/131/12/13

Keywords

  • approximation algorithm
  • average-case analysis
  • minimum feedback arc set
  • semi-random model

ASJC Scopus subject areas

  • Management of Technology and Innovation
  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'Sorting noisy data with partial information'. Together they form a unique fingerprint.

Cite this