IC Monday Seminars : Better approximation algorithms for classical optimization problems ?
Event details
| Date | 27.02.2012 |
| Hour | 16:15 › 17:30 |
| Speaker | Dr. Ola Svensson, Postdoctoral Researcher EPFL - IC Faculty candidate |
| Location | |
| Category | Conferences - Seminars |
Abstract:
Approximation algorithms are motivated by the fact that for many
important optimization problems we cannot hope to efficiently find an
optimal solution. Instead, we have to settle for second best - a
solution that is close to being optimal. Some of the earliest success
stories of this paradigm deal with fundamental optimization problems
arising in operations research, such as the problem of scheduling with
precedence constraints (Graham 66) and the traveling salesman problem
(Christofides 76).
In spite of significant effort, it remains unknown whether many of
these problems admit better algorithms. In this talk, we will discuss
recent progress on answering this question for some of the most
classical optimization problems, including the problems mentioned above.
In particular, we will focus on our new results for the traveling
salesman problem.
Biography:
Ola Svensson is a Post-Doc in Prof. Amin Shokrollahi's lab on
algorithms at EPFL. Before coming to EPFL, he spent 2 years as a
Post-Doc in Prof. Johan Håstad's group on approximation algorithms at
KTH and 3.5 years (out of which half a year was spent at MIT) as a PhD
student at IDSIA under the supervision of Dr. Monaldo Mastrolilli.
His research focuses on understanding the complexity of fundamental
optimization problems by both giving efficient (approximation)
algorithms and lower bounds.
Approximation algorithms are motivated by the fact that for many
important optimization problems we cannot hope to efficiently find an
optimal solution. Instead, we have to settle for second best - a
solution that is close to being optimal. Some of the earliest success
stories of this paradigm deal with fundamental optimization problems
arising in operations research, such as the problem of scheduling with
precedence constraints (Graham 66) and the traveling salesman problem
(Christofides 76).
In spite of significant effort, it remains unknown whether many of
these problems admit better algorithms. In this talk, we will discuss
recent progress on answering this question for some of the most
classical optimization problems, including the problems mentioned above.
In particular, we will focus on our new results for the traveling
salesman problem.
Biography:
Ola Svensson is a Post-Doc in Prof. Amin Shokrollahi's lab on
algorithms at EPFL. Before coming to EPFL, he spent 2 years as a
Post-Doc in Prof. Johan Håstad's group on approximation algorithms at
KTH and 3.5 years (out of which half a year was spent at MIT) as a PhD
student at IDSIA under the supervision of Dr. Monaldo Mastrolilli.
His research focuses on understanding the complexity of fundamental
optimization problems by both giving efficient (approximation)
algorithms and lower bounds.
Links
Practical information
- Informed public
- Free
- This event is internal
Contact
- Christine Moscioni