KIT | KIT-Bibliothek | Impressum | Datenschutz

Pareto Sums of Pareto Sets

Hespe, Demian ORCID iD icon 1; Sanders, Peter ORCID iD icon 1; Storandt, Sabine; Truschel, Carina; Gørtz, Inge Li [Hrsg.]; Farach-Colton, Martin [Hrsg.]; Puglisi, Simon J. [Hrsg.]; Herman, Grzegorz [Hrsg.]
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

In bi-criteria optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on efficient merging or combining of partial solutions and filtering of dominated solutions in the resulting sets. In this paper, we consider the task of computing the Pareto sum of two given Pareto sets A, B of size n. The Pareto sum contains all non-dominated points of the Minkowski sum M = {a+b|a ∈ A, b ∈ B}. Since the Minkowski sum has a size of n², but the Pareto sum C can be much smaller, the goal is to compute C without having to compute and store all of M. We present several new algorithms for efficient Pareto sum computation, including an output-sensitive one with a running time of 𝒪(n log n + nk) and a space consumption of 𝒪(n+k) for k = |C|. We also describe suitable engineering techniques to improve the practical running times of our algorithms and provide a comparative experimental study. As one showcase application, we consider preprocessing-based methods for bi-criteria route planning in road networks. Pareto sum computation is a frequent task in the preprocessing phase. ... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000163541
Veröffentlicht am 27.10.2023
Originalveröffentlichung
DOI: 10.4230/LIPIcs.ESA.2023.60
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2023
Sprache Englisch
Identifikator ISSN: 1868-8969
KITopen-ID: 1000163541
Erschienen in 31st Annual European Symposium on Algorithms (ESA 2023). Hrsg.: I. Li Gortz, M. Farach-Colton, S.J. Puglisi, G. Herman
Veranstaltung 31st 31st Annual European Symposium on Algorithms (Part of ALGO 2023) (ESA 2023), Amsterdam, Niederlande, 04.09.2023 – 08.09.2023
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten 1-17
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 274
Schlagwörter Minkowski sum, Skyline, Successive Algorithm
Nachgewiesen in Scopus
Globale Ziele für nachhaltige Entwicklung Ziel 11 – Nachhaltige Städte und Gemeinden
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page