Seminar: November 20, 2008

Yuri Makarychev, Microsoft Research

On the Advantage over Random for Maximum Acyclic Subgraph

Note non-standard day!

We will describe a new approximation algorithm for the Maximum 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. We will also describe our integrality gap instance, which was recently used by Guruswami, Manokaran, and Raghavendra to prove a UGC-inapproximability result for this problem.

This is joint work with Moses Charikar and Konstantin Makarychev (appeared at FOCS'07).