Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914011058012160 |
|---|---|
| author | Karathanasis, Konstantinos Kontogiannis, Spyros Zaroliagis, Christos |
| author_facet | Karathanasis, Konstantinos Kontogiannis, Spyros Zaroliagis, Christos |
| contents | A key task in multi-objective optimization is to compute the Pareto subset or frontier $P$ of a given $d$-dimensional objective space $F$; that is, a maximal subset $P\subseteq F$ such that every element in $P$ is not-dominated (it is not worse in all criteria) by any element in $F$. This process, called dominance-filtering, often involves handling objective spaces derived from either the union or the Minkowski sum of two given partial objective spaces which are Pareto sets themselves, and constitutes a major bottleneck in several multi-objective optimization techniques. In this work, we introduce three new data structures, ND$^{+}$-trees, QND$^{+}$-trees and TND$^{+}$-trees, which are designed for efficiently indexing non-dominated objective vectors and performing dominance-checks. We also devise three new algorithms that efficiently filter out dominated objective vectors from the union or the Minkowski sum of two Pareto sets. An extensive experimental evaluation on both synthetically generated and real-world data sets reveals that our new algorithms outperform state-of-art techniques for dominance-filtering of unions and Minkowski sums of Pareto sets, and scale well w.r.t. the number of $d\ge 3$ criteria and the sets' sizes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20689 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets Karathanasis, Konstantinos Kontogiannis, Spyros Zaroliagis, Christos Data Structures and Algorithms A key task in multi-objective optimization is to compute the Pareto subset or frontier $P$ of a given $d$-dimensional objective space $F$; that is, a maximal subset $P\subseteq F$ such that every element in $P$ is not-dominated (it is not worse in all criteria) by any element in $F$. This process, called dominance-filtering, often involves handling objective spaces derived from either the union or the Minkowski sum of two given partial objective spaces which are Pareto sets themselves, and constitutes a major bottleneck in several multi-objective optimization techniques. In this work, we introduce three new data structures, ND$^{+}$-trees, QND$^{+}$-trees and TND$^{+}$-trees, which are designed for efficiently indexing non-dominated objective vectors and performing dominance-checks. We also devise three new algorithms that efficiently filter out dominated objective vectors from the union or the Minkowski sum of two Pareto sets. An extensive experimental evaluation on both synthetically generated and real-world data sets reveals that our new algorithms outperform state-of-art techniques for dominance-filtering of unions and Minkowski sums of Pareto sets, and scale well w.r.t. the number of $d\ge 3$ criteria and the sets' sizes. |
| title | Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.20689 |