Publikation:

Pareto Sums of Pareto Sets

Lade...
Vorschaubild

Dateien

Hespe_2-1eayfuk87e0x70.PDF
Hespe_2-1eayfuk87e0x70.PDFGröße: 1.89 MBDownloads: 1

Datum

2023

Autor:innen

Hespe, Demian
Sanders, Peter

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
oops

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Gold
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

31st Annual European Symposium on Algorithms (ESA 2023). Dagstuhl: Schloss Dagstuhl : Leibniz-Zentrum für Informatik, 2023, 60. LIPIcs - Leibniz International Proceedings in Informatics. 274. ISSN 1868-8969. ISBN 978-3-95977-295-2. Verfügbar unter: doi: 10.4230/LIPIcs.ESA.2023.60

Zusammenfassung

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. We show that using our algorithms with an output-sensitive space consumption allows to tackle larger instances and reduces the preprocessing time compared to algorithms that fully store M.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Minkowski sum, Skyline, Successive Algorithm

Konferenz

31st Annual European Symposium on Algorithms (ESA 2023), 4. Sept. 2023 - 6. Sept. 2023, Amsterdam, Netherlands
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690HESPE, Demian, Peter SANDERS, Sabine STORANDT, Carina TRUSCHEL, 2023. Pareto Sums of Pareto Sets. 31st Annual European Symposium on Algorithms (ESA 2023). Amsterdam, Netherlands, 4. Sept. 2023 - 6. Sept. 2023. In: 31st Annual European Symposium on Algorithms (ESA 2023). Dagstuhl: Schloss Dagstuhl : Leibniz-Zentrum für Informatik, 2023, 60. LIPIcs - Leibniz International Proceedings in Informatics. 274. ISSN 1868-8969. ISBN 978-3-95977-295-2. Verfügbar unter: doi: 10.4230/LIPIcs.ESA.2023.60
BibTex
@inproceedings{Hespe2023-08-30Paret-67878,
  year={2023},
  doi={10.4230/LIPIcs.ESA.2023.60},
  title={Pareto Sums of Pareto Sets},
  number={274},
  isbn={978-3-95977-295-2},
  issn={1868-8969},
  publisher={Schloss Dagstuhl : Leibniz-Zentrum für Informatik},
  address={Dagstuhl},
  series={LIPIcs - Leibniz International Proceedings in Informatics},
  booktitle={31st Annual European Symposium on Algorithms (ESA 2023)},
  author={Hespe, Demian and Sanders, Peter and Storandt, Sabine and Truschel, Carina},
  note={Article Number: 60}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/67878">
    <dc:language>eng</dc:language>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/67878/1/Hespe_2-1eayfuk87e0x70.PDF"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/67878/1/Hespe_2-1eayfuk87e0x70.PDF"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:issued>2023-08-30</dcterms:issued>
    <dc:creator>Sanders, Peter</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Sanders, Peter</dc:contributor>
    <dcterms: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. We show that using our algorithms with an output-sensitive space consumption allows to tackle larger instances and reduces the preprocessing time compared to algorithms that fully store M.</dcterms:abstract>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:title>Pareto Sums of Pareto Sets</dcterms:title>
    <dc:creator>Hespe, Demian</dc:creator>
    <dc:contributor>Truschel, Carina</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/67878"/>
    <dc:creator>Truschel, Carina</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-09-28T12:24:20Z</dc:date>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:contributor>Hespe, Demian</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-09-28T12:24:20Z</dcterms:available>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Unbekannt
Diese Publikation teilen