Speaker: Ilias Diakonikolas
Title: Approximation in Multiobjective Optimization
In multi-objective 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 has typically exponential size and hence we cannot efficiently construct
the full curve. Instead, we want to compute efficiently a small set of solutions
(as small as possible) that provides a "good enough" representation (as good as possible)
of the whole design space.
In recent years we initiated a systematic investigation to develop the theory of multi-objective
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?
The talk will survey joint works with Mihalis Yannakakis.