IC Mondays seminars - Approximation in Multiobjective Optimization
Event details
| Date | 12.04.2010 |
| Hour | 16:15 |
| Speaker | Dr.Ilias Diakonikolas, Columbia University, Computer Science Department |
| Location |
INM 202
|
| Category | Conferences - Seminars |
Abstract
In multiobjective optimization, solutions to an optimization problem are evaluated with respect to several cost criteria, and we are interested in a class of solutions that capture the trade-off between these objectives, the so-called Pareto curve. The problem is that the Pareto curve is typically prohibitively large (or even infinite) and hence we cannot construct the full curve. Instead, we want to efficiently compute a small set of solutions (as small as possible) that provides a "good enough" representation (as good as possible) of the whole design space. This has been the underlying goal of much of the research in the area, where many heuristics have been proposed for this purpose, usually however without any performance guarantees or complexity analysis.
In recent years, we initiated a systematic investigation to develop the theory of multiobjective approximation along similar rigorous lines as the approximation of single-objective problems. We address the problem of efficiently computing a succinct approximation to the Pareto curve using as few points as possible. If we are to select only a certain number of solutions, how shall we pick them so that they represent as accurately as possible the whole spectrum of possibilities?
I will present general methods for computing efficiently succinct approximations to the Pareto curve for broad classes of problems, and show how they can be applied to particular well-studied problems (such as multiobjective shortest paths, linear programming, etc)
(The talk is based on joint works with Mihalis Yannakakis.)
Biography
Ilias Diakonikolas received his undergraduate degree in Electrical and Computer Engineering from the National Technical University of Athens. He is currently pursuing a Ph.D. in Computer Science at Columbia University under the supervision of Professor Mihalis Yannakakis.
Ilias' research interests include areas of theoretical computer science such as approximation algorithms, computational complexity, computational learning and property testing. His thesis work focuses in the development of a coherent algorithmic theory for multiobjective optimization problems. His work in this area has been honored by the INFORMS society.
Links
Practical information
- General public
- Free
Contact
- G.Rochat