# One-Exact Approximate Pareto Sets

arXiv: https://arxiv.org/abs/1908.10561 · HTML: https://mlsanity.com/paper/1908.10561/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2019.

## Built on by (most cited first, 1 of 1)

- [Exact and approximate determination of the Pareto set using minimal correction subsets](https://mlsanity.com/paper/2204.06908/) (2022)

## Abstract (arXiv)

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.