REPORTS > DETAIL:
Paper:
TR07-104 | 15th September 2007 00:00
On the Advantage over Random for Maximum Acyclic Subgraph
TR07-104 Authors: Moses Charikar, Konstantin Makarychev, Yury Makarychev
Publication: 22nd October 2007 16:07
Downloads: 196
Keywords:
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 + delta) fraction of all edges, our algorithm finds an acyclic subgraph with (1/2 + Omega(delta/ log n)) fraction of all edges.