On the Advantage over Random for Maximum Acyclic Subgraph
Moses Charikar, Konstantin Makarychev, Yury Maka · 2007
In this paper we present a new approximation algorithm for the Max Acyclic Subgraph problem. Given an instance where the maximum acyclic subgraph contains 1/2 + delta fraction of all edges, our algorithm finds an acyclic subgraph with 1/2 + Omega(delta/ log n) fraction of all edges.