Campus Event Calendar
Event Entry
What and Who
25 Years of Isolation Lemma
Bodo Manthey
University of Twente
Antrittsvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 26 April 2012
14:15
45 Minutes
E1 3
HS 002
Saarbrücken
Abstract
The isolation lemma has been proved in 1987 in order to design efficient parallel algorithms for the matching problem. Roughly speaking, it states that a small amount of randomness suffices to make the optimum solution of an optimization problem unique.
Since its invention, the isolation lemma has proved useful in a variety of contexts. We sketch some variants of the isolation lemma and apply them to obtain smoothed analyses of, for instance, integer programming, min-cost flow, and belief propagation.
Contact
gk-sek
--email hidden
passcode not visible
logged in users only
gk-sek, 04/19/2012 12:09 -- Created document.