Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MAXIMUM ACYCLIC SUBGRAPH:
Reports tagged with Maximum Acyclic Subgraph:
TR07-104 | 15th September 2007
Moses Charikar, Konstantin Makarychev, Yury Makarychev

On the Advantage over Random for Maximum Acyclic Subgraph

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.

more >>>



ISSN 1433-8092 | Imprint