Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other
Problems
Ilias Diakonikolas and Mihalis Yannakakis
10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2007
Nicholson student paper competition honorable mention, 2009
(awarded at INFORMS meeting, October 2009,
Abstract:
We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy $\epsilon$ the Pareto curve of a multiobjective optimization problem. We show that for a broad class of bi-objective problems (containing many important widely studied problems such as shortest paths, spanning tree, and many others), we can compute in polynomial time an $\epsilon$-Pareto set that contains at most twice as many solutions as the minimum such 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.
Conference version: [PDF]
Full version: [PDF] (updated April 2009) [SIAM]