[Colloquium] Talk by Yury Makarychev, Princeton University on November 20, 2008

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Thursday, November 20, 2008
Time: 3:45 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Yury Makarychev

From:		Princeton University

Web page:	 http://www.cs.princeton.edu/~ymakaryc/

Title:    On the Advantage over Random for Maximum Acyclic Subgraph

Abstract:  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).

Refreshments will be served prior to the talk in RY 255 at 3:00.