M. Yannakakis
When evaluating different solutions from a design space, it is often the case that more than one criteria come into play. The trade-off between the different criteria is captured by the so-called Pareto curve. The Pareto curve has typically an exponential number of points. However, it turns out that, under general conditions, there is a polynomially succinct curve that approximates the Pareto curve within any desired accuracy. This talk will discuss problems concerning the efficient computation of good approximate solutions for multiobjective problems. In the first part of the talk, we address the question of when an approximate Pareto curve can be computed in polynomial time. We discuss general conditions under which this is the case and relate the multiobjective approximation to the single objective case. In the second part of the talk, we address the problem of computing efficiently a good approximation of the trade-off curve using as few solutions (points) as possible. If we are to select only a limited number of solutions, how shall we pick them so that they represent as accurately as possible the spectrum of possibilities?
Keywords: Multiobjective Optimization
Scheduled
TE1-P2 Plenary. Approximation of multiobjective optimization problems
June 10, 2021 4:15 PM
1 - GB Dantzig
