Center for Web Research D.C.S.

		University of Chile

Publish your event on the CRW Website

In order to have your event announced in our website, contact our webmaster, detailing:

  • Event name
  • Contact address
    (Web Page and E-mail)
  • Event description
  • Important dates

If possible, include a Spanish version as well.

Conferences and Courses

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.


Department of Computer Sciences
University of Chile
Blanco Encalada #2120
Santiago, Chile

Millenium Science Initiative Questions/Comments: cwr@dcc.uchile.cl
Last modification:
Search Services in: Go to todocl.cl

The Center for Web Research (CWR) is possible thanks to the Millenium Science Initiative Program
Millenium Science Initiative, Ministry of Planning and Cooperation - Government of Chile

Valid HTML 4.01! Valid CSS!