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
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
criteria is captured by the so-called Pareto curve.
The Pareto curve has typically an exponential number of points.
turns out that, under general conditions, there is a polynomially
that approximates the Pareto curve within any desired accuracy.
In the first part of the talk we address the question of when
approximate Pareto curve can be computed in polynomial time. We
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
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
represent as accurately as possible the spectrum of possibilities?
(The talk is based on joint works with Christos Papadimitriou,
Vassilvitskii and Ilias Diakonikolas.)
Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor
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
Foundations of Computer Science, the ACM Symposium on Theory of
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.