Conference paper
Integrality gaps for sherali-adams relaxations
Moses Charikar, Konstantin Makarychev, et al.
STOC 2009
Conference paper
On the advantage over random for maximum acyclic subgraph
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 + δ fraction of all edges, our algorithm finds an acyclic subgraph with 1/2 + Ω(δ/ log n) fraction of all edges. © 2007 IEEE.
Related
Howard Karloff, Flip Korn, et al.
STACS 2011
Guojing Cong, Konstantin Makarychev
IPDPS 2011
Moses Charikar, Joseph Seffi Naor, et al.
IEEE/ACM Transactions on Networking