IC Colloquium : Combinatorial Optimization with Noisy Inputs : How Can We Separate the Wheat From the Chaff?
Event details
| Date | 26.11.2012 |
| Hour | 16:15 › 17:30 |
| Speaker | Peter Widmayer, ETH Zurich |
| Location | |
| Category | Conferences - Seminars |
Abstract
Real world data are almost always noisy, and an exact solution to a noisy input of an optimization problem is not what we really want. We propose a way to ignore the noisy part of the given data, while preserving the meaningful part, that is, to separate the information in the data from the noise. We require simply two input instances for this purpose, and we show how to extract the information in these instances. Whenever an instance generator with a strongly peaked distribution hides behind both inputs, our approach shall return 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 tree. We discuss implications of the approach on the algorithmic complexity of these problems.
Biography
Peter Widmayer got a PhD in Karlsruhe in 1983, went for a postdoc to the IBM T.J. Watson Research Center, got a habilitation and venia legendi in Karlsruhe in 1986 and 1987, moved to Freiburg University (Germany) in 1988 and then to ETH Zurich in 1992.
His research centers around algorithms and data structures for combinatorial and geometric problems that are motivated from real world applications.
Real world data are almost always noisy, and an exact solution to a noisy input of an optimization problem is not what we really want. We propose a way to ignore the noisy part of the given data, while preserving the meaningful part, that is, to separate the information in the data from the noise. We require simply two input instances for this purpose, and we show how to extract the information in these instances. Whenever an instance generator with a strongly peaked distribution hides behind both inputs, our approach shall return 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 tree. We discuss implications of the approach on the algorithmic complexity of these problems.
Biography
Peter Widmayer got a PhD in Karlsruhe in 1983, went for a postdoc to the IBM T.J. Watson Research Center, got a habilitation and venia legendi in Karlsruhe in 1986 and 1987, moved to Freiburg University (Germany) in 1988 and then to ETH Zurich in 1992.
His research centers around algorithms and data structures for combinatorial and geometric problems that are motivated from real world applications.
Links
Practical information
- Informed public
- Free
Organizer
- Host : Aleksander Madry
Contact
- Christine Moscioni/Simone Muller