TY - GEN
T1 - On the advantage over random for maximum acyclic subgraph
AU - Charikar, Moses
AU - Makarychev, Konstantin
AU - Makarychev, Yury
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=46749087468&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=46749087468&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2007.4389531
DO - 10.1109/FOCS.2007.4389531
M3 - Conference contribution
AN - SCOPUS:46749087468
SN - 0769530109
SN - 9780769530109
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 625
EP - 633
BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007
Y2 - 20 October 2007 through 23 October 2007
ER -