Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems

I. Diakonikolas, M. Yannakakis

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy ε the Pareto curve of a multiobjective optimization problem. We show that for a broad class of biobjective problems (containing many important widely studied problems such as shortest paths, spanning tree, matching, and many others), we can compute in polynomial time an ε-Pareto set that contains at most twice as many solutions as the minimum set. Furthermore we show that the factor of 2 is tight for these problems; i.e., it is NP-hard to do better. We present upper and lower bounds for three or more objectives, as well as for the dual problem of computing a specified number k of solutions which provide a good approximation to the Pareto curve.
Original languageEnglish
Pages (from-to)1340-1371
Number of pages32
JournalSIAM Journal on Computing
Volume39
Issue number4
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems'. Together they form a unique fingerprint.

Cite this