One-exact approximate Pareto sets
| Autor: | Arne Herzel, Cristina Bazgan, Clemens Thielen, Stefan Ruzika, Daniel Vanderpooten |
|---|---|
| Přispěvatelé: | Department of Mathematics, University of Kaiserslautern, Technische Universität Kaiserslautern (TU Kaiserslautern), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Fachbereich Mathematik [Kaiserslautern] |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Class (set theory) Control and Optimization 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology Management Science and Operations Research 01 natural sciences Set (abstract data type) Combinatorics Cardinality Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] 0101 mathematics Mathematics 021103 operations research Spanning tree Biobjective optimization Applied Mathematics Pareto principle [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Computer Science Applications ddc Multiobjective optimization problem Shortest path problem |
| Zdroj: | Journal of Global Optimization Journal of Global Optimization, Springer Verlag, 2021, 80 (1), pp.87-115. ⟨10.1007/s10898-020-00951-7⟩ |
| ISSN: | 0925-5001 1573-2916 |
| DOI: | 10.1007/s10898-020-00951-7⟩ |
| Popis: | 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+\varepsilon , \dots , 1+\varepsilon )$$ ( 1 + ε , ⋯ , 1 + ε ) -approximate Pareto set (also called an $$\varepsilon $$ ε -Pareto set). Similarly, in this article, we characterize the class of multiobjective optimization problems having a polynomial-time computable approximate $$\varepsilon $$ ε -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 $$\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 cardinality of the set can be obtained efficiently. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink