  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.
