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. We point out that, under general conditions, there is a polynomially succinct curve that approximates the Pareto curve within any desired accuracy, and give conditions under which this approximate Pareto curve can be constructed in polynomial time. We discuss in more detail the class of linear multiobjective problems, and multiobjective query optimization.

Brief Bio

Mihalis Yannakakis received the Diploma in Electrical Engineering from the National Technical University of Athens, Greece, in 1975, and the Ph.D. degree in Computer Science from Princeton University in 1979. He joined Bell Laboratories in 1978 where he worked until 2001, serving as Director of the Computing Principles Research Department since 1991.He joined Avaya Laboratories in July 2001, where he is Director of Computing Principles Research. His research interests include algorithms and complexity, combinatorial optimization, databases, testing and verification. Dr. Yannakakis is the Editor-in-chief of the SIAM Journal on Computing and serves on the editorial boards of several other journals. He has served on the program committees and chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems. Dr. Yannakakis is a Fellow of the ACM and a Bell Labs Fellow.