Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> MARCH 5: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
MARCH 5: Theory CS Seminar
Event date: Friday, March 05, 2010, at 11:10 AM
Location: Galbraith Bldg, Rm. 244
Speaker: Ilias Diakonikolas
Columbia University
Title: Approximation in Multiobjective Optimization
Abstract: In multi-objective optimization, solutions to an optimization problem are evaluated with respect to several cost criteria, and we are interested in a class of solutions that capture the trade-off between these objectives, the so-called Pareto curve. The problem is that the Pareto curve has typically exponential size and hence we cannot efficiently construct the full curve. Instead, we want to compute efficiently a small set of solutions (as small as possible) that provides a "good enough" representation (as good as possible) of the whole design space.
In recent years we initiated a systematic investigation to develop the theory of multi-objective approximation along similar rigorous lines as the approximation of single objective problems. We address the problem of efficiently computing a succinct approximation to the Pareto curve using as few 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 whole spectrum of possibilities?
The talk will survey joint works with Mihalis Yannakakis.