BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Combinatorial Optimization with Noisy Inputs : How
  Can We Separate the Wheat From the Chaff?
DTSTART:20121126T161500
DTEND:20121126T173000
DTSTAMP:20260408T085638Z
UID:bedf6f990e4f4393d833c7865ed230690021a8d26620c9604685edfc
CATEGORIES:Conferences - Seminars
DESCRIPTION:Peter Widmayer\, ETH Zurich\nAbstract\nReal world data are alm
 ost always noisy\, and an exact solution to a noisy input of an optimizati
 on problem is not what we really want. We propose a way to ignore the nois
 y part of the given data\, while preserving the meaningful part\, that is\
 , to separate the information in the data from the noise. We require simpl
 y two input instances for this purpose\, and we show how to extract the in
 formation in these instances. Whenever an instance generator with a strong
 ly peaked distribution hides behind both inputs\, our approach shall retur
 n a close to optimum solution. We demonstrate the approach at a few simple
  algorithmic problems\, such as finding a minimum in a set of numbers\, a 
 maximum subarray\, a shortest path in a graph\, and a minimum spanning tre
 e. We discuss implications of the approach on the algorithmic complexity o
 f these problems.\n\nBiography \nPeter Widmayer got a PhD in Karlsruhe in 
 1983\, went for a postdoc to the IBM T.J. Watson Research Center\, got a h
 abilitation and venia legendi in Karlsruhe in 1986 and 1987\, moved to Fre
 iburg University (Germany) in 1988 and then to ETH Zurich in 1992.\nHis re
 search centers around algorithms and data structures for combinatorial an
 d geometric problems that are motivated from real world applications.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR