Subject: Re: Special talk this friday by Christos Papadimitriou (fwd)
From: Mark Seigle (seigle@cs.washington.edu)
Date: Mon Apr 30 2001 - 10:10:22 PDT
I'd like to attend this as well.
Mark
On Mon, 30 Apr 2001, Todd D Millstein wrote:
>
> 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
>
_______________________________________________
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 - 10:11:05 PDT