Sorting Noisy Data with Partial Information
January 30, 2013
In this talk, we look at minimum Feedback Arc Set (FAS), a basic optimization problem on directed graphs. The problem asks to find the minimum set of edges (arcs) whose removal makes a given graph a directed acyclic graph (DAG). This is equivalent to finding an ordering of the vertices, which minimizes the number of backward edges (according to the ordering). The interest in FAS stems from its numerous applications in sorting and ranking based on pairwise information, removing cyclic dependencies, simplifying the analysis of feedback systems etc. However, the best known algorithm for this problem only gives a polylogarithmic approximation in the worst-case, and constant factor approximations have been elusive.

Since real-world instances are unlikely to behave like worst-case instances, a compelling question is : can we design better algorithms for realistic average case instances? We propose two realistic average-case models for the problem, and present new approximation algorithms which obtain a PTAS and constant factor approximations in these two models.

Based on joint work with Konstantin Makarychev and Yury Makarychev.