Centro de Investigación de la Web D.C.C. - 

		Universidad de Chile

Publique su evento en el CIW

Si usted desea que su evento sea mencionado en el sitio Web del Centro de Investigación de la Web, escriba al Webmaster indicando:

  • Nombre del evento

  • Direcciones de contacto
    (Página Web y E-mail)

  • Descripción del evento

  • Fechas importantes

De ser posible incluya los mismos datos en inglés

Charla: Computing Efficiently Succinct Trade-off Curves

SPEAKER: Mihalis Yannakakis
Columbia University

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

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


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


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.


Departamento de Ciencias de la Computación
Universidad de Chile
Blanco Encalada #2120
Santiago, Chile

iniciativa cientifica milenio Preguntas/Comentarios: ciw@dcc.uchile.cl
Ultima modificación:
Servicios de búsqueda por: Ir a todocl.cl

El Centro de Investigación de la Web (CIW) es posible gracias al Programa Iniciativa Científica Milenio
Iniciativa Científica Milenio, Ministerio de Planificación y Cooperación - Gobierno de Chile

Valid HTML 4.01! Valid CSS!