Subject: Special talk this friday by Christos Papadimitriou (fwd)
From: Todd D Millstein (todd@cs.washington.edu)
Date: Mon Apr 30 2001 - 09:01:21 PDT
Christos Papadimitriou is speaking this Friday at 3pm. I'd like to go
hear him, and I wonder if there are enough other people interested in
hearing this future Turing award winner to move the group meeting this
week. In my (albeit limited) experience, Papadimitriou gives great talks,
usually explaining fundamental ideas in intuitive ways. And he's got this
very unique booming voice that gives him instant authority.
Todd
---------- Forwarded message ----------
Date: Sun, 29 Apr 2001 22:44:22 -0700
From: Anna Karlin <karlin@cs.washington.edu>
To: theory-group <theory-group@cs.washington.edu>
Subject: Special talk this friday by Christos Papadimitriou
TIME & PLACE: Friday, May 4, 3pm, Sieg Hall 322
TITLE: The Complexity of Tradeoffs
SPEAKER: Christos Papadimitriou, UC Berkeley
In Computer Science we have always been interested (increasingly as the
context of computation becomes more complex) in tradeoffs, situations in
which a solution to an optimization problem must be evaluated with
respect to several cost criteria. Such is precisely the object of
study of Multiobjective Optimization, a research area in the interface
between Operations Research and Economics. The main object of interest
in that field is the Pareto set, the set of all "undominated" solutions,
those that cannot be improved in all objectives ---exactly what in CS
we would call "a trade-off." Unfortunately, the Pareto set is, in
general, of exponential size; hence the basic computational problem of
that field is a priori hopeless, and research in it has either been
non-computational (e.g., treating the multi-objective problem as a
conceptual device whereby the true, single objective, known only to the
decision-maker will be revealed by interaction), or empirical approaches
that ignore the exponential obstacle. In recent joint work with Mihalis
Yannakakis we show that, under very general conditions, there is a
polynomially small set of solutions that approximates the Pareto curve
arbitrarily closely; hence multiobjective optimization can be studied as
a computational problem. We also give general conditions under which
this approximate Pareto set can be constructed in polynomial in the size
of the instance and the desired approximation, and apply them to many
natural problems ---including database query optimziation, and a
cost-time-quality trade-off for optimizing access to the world-wide web,
in a model first studied by Etzioni et al. (which was actually the
original motivation for this work).
_______________________________________________
Cecil mailing list
Cecil@cs.washington.edu
http://majordomo.cs.washington.edu/mailman/listinfo/cecil
This archive was generated by hypermail 2b25 : Mon Apr 30 2001 - 09:02:05 PDT