One-exact approximate Pareto sets
- PDF / 633,725 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 229 Views
One-exact approximate Pareto sets Arne Herzel1,3 · Cristina Bazgan2 · Stefan Ruzika1 · Clemens Thielen3 · Daniel Vanderpooten2 Received: 7 May 2019 / Accepted: 20 September 2020 © The Author(s) 2020
Abstract Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the Foundations of Computer Science (FOCS), pp 86–92, 2000) show that the polynomial-time solvability of a certain auxiliary problem determines the class of multiobjective optimization problems that admit a polynomial-time computable (1+ε, . . . , 1+ε)-approximate Pareto set (also called an ε-Pareto set). Similarly, in this article, we characterize the class of multiobjective optimization problems having a polynomial-time computable approximate ε-Pareto set that is exact in one objective by the efficient solvability of an appropriate auxiliary 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 optimization problems from this class, we provide an algorithm that computes a one-exact ε-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 cardinality of the set can be obtained efficiently. Keywords Multiobjective optimization · Approximation algorithm · Approximate Pareto set · scalarization Mathematics Subject Classification 90C29 · 90C59
1 Introduction In many cases, real-world optimization problems involve several conflicting objectives, e.g., the minimization of cost and time in transportation systems or the maximization of profit and security in investments. In this context, solutions optimizing all objectives simultaneously
This work was supported by the bilateral cooperation project “Approximation methods for multiobjective optimization problems” funded by the German Academic Exchange Service (DAAD, Project-ID 57388848) and by Campus France, PHC PROCOPE 2018 (Project No. 40407WF) as well as by the DFG Grants RU 1524/6-1 and TH 1852/4-1.
B
Arne Herzel [email protected]
Extended author information available on the last page of the article
123
Journal of Global Optimization
usually do not exist. Therefore, in order to support decision making, so-called efficient (or Pareto optimal) solutions achieving a good compromise among the objectives are considered. More formally, a solution is said to be efficient if any other solution that is better in some objective is necessarily worse in at least one other objective. The image of an efficient solution in the objective space is called a nondominated point. When no prior preference information is available, one main goal of multiobjective optimization is to determine the set of all nondominated points and provide, for each of them, one corresponding efficient solution. Several results in the literature, however, show that multiobjective optimiza
Data Loading...
