Publication
FOCS 2007
Conference paper
On the advantage over random for maximum acyclic subgraph
Abstract
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 + δ fraction of all edges, our algorithm finds an acyclic subgraph with 1/2 + Ω(δ/ log n) fraction of all edges. © 2007 IEEE.