On the Advantage over Random for Maximum Acyclic Subgraph
(Citations: 7)
In this paper we present a new approximation algo- rithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains 1/2+� fraction of all edges, our algorithm finds an acyclic subgraph with1/2 + (�/logn) fraction of all edges.