Campus Event Calendar
Event Entry
What and Who
Approximation Algorithms Reading Group
Julian
Max-Planck-Institut für Informatik - D1
Lecture
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 13 December 2007
14:30
-- Not specified --
E1 4
Rotunda 3rd floor
Saarbrücken
Abstract
Title: Randomized Local Ratio
Abstract: The Local Ratio framework can be easily extended to allow
randomization when choosing the weight decomposition and constructing
the feasible primal solution. In this lecture we will see two
applications of this idea. First, I'll go over Pitt's 2-approximation
for vertex cover; then I'll cover the 3-approximation of Ailon,
Charikar and Newman for minimum feedback arc set in tournament graphs.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 12/11/2007 08:57 -- Created document.