  Papadimitriou and Yannakakis show that the polynomial-time solvability of a
certain singleobjective problem determines the class of multiobjective
optimization problems that admit a polynomial-time computable $(1+\varepsilon,
\dots , 1+\varepsilon)$-approximate Pareto set (also called an
$\varepsilon$-Pareto set). Similarly, in this article, we characterize the
class of problems having a polynomial-time computable approximate
$\varepsilon$-Pareto set that is exact in one objective by the efficient
solvability of an appropriate singleobjective problem. This class includes
important problems such as multiobjective shortest path and spanning tree, and
the approximation guarantee we provide is, in general, best possible.
Furthermore, for biobjective problems from this class, we provide an algorithm
that computes a one-exact $\varepsilon$-Pareto set of cardinality at most twice
the cardinality of a smallest such set and show that this factor of 2 is best
possible. For three or more objective functions, however, we prove that no
constant-factor approximation on the size of the set can be obtained
efficiently.
