Charla: Computing Efficiently Succinct Trade-off Curves

SPEAKER: Mihalis Yannakakis
Columbia University

PLACE: TBA
TIME: 3:00 pm
DATE: Friday, August 25

ORGANIZERS:
CIW/DCC Centro de Investigacion de la Web &
Depto. de Cs. de la Computacion
CMM/DIM Seminario de Matematicas Discretas

ABSTRACT

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.

In the first part of the talk we address the question of when such 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 certain number of solutions, how shall we pick them so that they
represent as accurately as possible the spectrum of possibilities?

(The talk is based on joint works with Christos Papadimitriou, Sergei
Vassilvitskii and Ilias Diakonikolas.)

BIO

Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of
Computer Science at Columbia University. Prior to joining Columbia,
he was Director of the Computing Principles Research Department
at Bell Labs and at Avaya Labs,
and Professor of Computer Science at Stanford University.
Dr. Yannakakis received his PhD from Princeton University.
His research interests include algorithms, complexity, optimization,
databases, testing and verification.
He has served on the editorial boards of several journals,
including as the past editor-in-chief of the SIAM Journal on Computing,
and has chaired various conferences, including the IEEE Symposium on
Foundations of Computer Science, the ACM Symposium on Theory of Computing
and the ACM Symposium on Principles of Database Systems.
Dr. Yannakakis is a Fellow of the ACM, a Bell Labs Fellow, and
a recipient of the Knuth Prize.