Title :
On the Advantage over Random for Maximum Acyclic Subgraph
Author :
Charikar, Moses ; Makarychev, Konstantin ; Makarychev, Yury
Author_Institution :
Princeton Univ., Princeton
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.
Keywords :
graph theory; random processes; approximation algorithm; maximum acyclic subgraph; Approximation algorithms; Computer science; Data mining; Engineering profession; Mathematical programming;
Conference_Titel :
Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on
Conference_Location :
Providence, RI
Print_ISBN :
978-0-7695-3010-9
DOI :
10.1109/FOCS.2007.65
