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


TE1-P2 Plenary. Approximation of multiobjective optimization problems
June 10, 2021  4:15 PM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.