[Colloquium] TTIC Talk: Ilias Diakonikolas, Columbia University

[Julia MacGlashan]

When:             *Tuesday, Feb 16 @ 11:00am*

Where:           * TTI-C Conference Room #526*, 6045 S Kenwood Ave


Who:              * **Ilias Diakonikolas*, Columbia University


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 thatcapture 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.

Host:              Yury Makarychev, yury at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100215/67e68ab6/attachment.htm