University Homepage School Homepage School Contacts School Search

Computing Efficiently Succinct Trade-off Curves

Mihalis Yannakakis
9.30, Friday 21 May 2004

We discuss problems in multiobjective optimization, in which solutions to a combinatorial optimization problem are evaluated with respect to several cost criteria, and we are interested in the trade-off between these objectives, 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. We examine in more detail the class of linear multiobjective problems, 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 points (solutions) as possible. We present general algorithms and associated lower bounds for 2 and 3 objectives, and for an arbitrary number of objectives.

(Joint work with Christos Papadimitriou and Sergei Vassilvitskii.)