[Colloquium] Reminder: Talk by Yury Makarychev Today

[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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20081120/56562d7b/attachment.htm