ALGO Talk - One-exact ε-Pareto sets

Talk by Arne Herzel, University of Kaiserslautern, 23 April 2021

Abstract:

For multiobjective optimization problems, an ε-Pareto set is a set of feasible solutions that, for each (efficient) solution, contains a solution that dominates it up to a factor of 1+ε. It is well known that the polynomial-time solvability of a certain single-objective problem determines the class of multiobjective optimization problems that admit a polynomial-time computable ε-Pareto set. Similarly, in this talk, we characterize the class of problems having a polynomial-time computable ε-Pareto set that optimizes one objective function exactly by the efficient solvability of an appropriate single-objective 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 adaptive algorithm that computes a one-exact ε-Pareto set of cardinality at most twice the cardinality of a smallest such set.