Keywords (1)

Academic
Publications
On the Advantage over Random for Maximum Acyclic Subgraph

On the Advantage over Random for Maximum Acyclic Subgraph,10.1109/FOCS.2007.65,Moses Charikar,Konstantin Makarychev,Yury Makarychev

On the Advantage over Random for Maximum Acyclic Subgraph  
BibTex | RIS | RefWorks Download
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.
Published in 2007.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.