Document Open Access Logo

Pareto Sums of Pareto Sets

Authors Demian Hespe , Peter Sanders , Sabine Storandt , Carina Truschel

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.60.pdf
  • Filesize: 1.46 MB
  • 17 pages

Document Identifiers

Author Details

Demian Hespe
  • Karlsruhe Institute of Technology, Germany
Peter Sanders
  • Karlsruhe Institute of Technology, Germany
Sabine Storandt
  • University of Konstanz, Germany
Carina Truschel
  • University of Konstanz, Germany

Funding

  • Sanders, Peter: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 882500).
  • Truschel, Carina: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project-ID 251654672 – TRR 161.

Cite As Get BibTex

Demian Hespe, Peter Sanders, Sabine Storandt, and Carina Truschel. Pareto Sums of Pareto Sets. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.60

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Minkowski sum
  • Skyline
  • Successive Algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K Agarwal, Eyal Flato, and Dan Halperin. Polygon decomposition for efficient construction of minkowski sums. Computational Geometry, 21(1-2):39-61, 2002. Google Scholar
  2. Saman Ahmadi, Guido Tack, Daniel D Harabor, and Philip Kilby. Bi-objective search with bi-directional a*. In Proceedings of the International Symposium on Combinatorial Search, volume 12, pages 142-144, 2021. Google Scholar
  3. Alex M Andrew. Another efficient algorithm for convex hulls in two dimensions. In Information Processing Letters, volume 9.5, pages 216-219. Elsevier, 1979. Google Scholar
  4. Christian Artigues, Marie-José Huguet, Fallou Gueye, Frédéric Schettini, and Laurent Dezou. State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths. Transportation Research Part C: Emerging Technologies, 27:233-259, 2013. Google Scholar
  5. Bernard Chazelle and Leonidas J Guibas. Fractional cascading: A data structuring technique with geometric applications. In Automata, Languages and Programming: 12th Colloquium Nafplion, Greece, July 15-19, 1985, pages 90-100. Springer, 2005. Google Scholar
  6. Wei-Mei Chen, Hsien-Kuei Hwang, and Tsung-Hsi Tsai. Maxima-finding algorithms for multidimensional samples: A two-phase approach. Computational Geometry, 45(1-2):33-53, 2012. Google Scholar
  7. Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. OR-spektrum, 22:425-460, 2000. Google Scholar
  8. Stephan Erb, Moritz Kobitzsch, and Peter Sanders. Parallel bi-objective shortest paths using weight-balanced b-trees with bulk updates. In Experimental Algorithms: 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29-July 1, 2014. Proceedings 13, pages 111-122. Springer, 2014. Google Scholar
  9. Stefan Funke and Sabine Storandt. Personalized route planning in road networks. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1-10, 2015. Google Scholar
  10. Antoine Kerbérénès, Daniel Vanderpooten, and Jean-Michel Vanpeperstraete. Computing efficiently the nondominated subset of a set sum. International Transactions in Operational Research, 2022. Google Scholar
  11. David G Kirkpatrick and Raimund Seidel. Output-size sensitive algorithms for finding maximal vectors. In Proceedings of the First Annual Symposium on Computational Geometry, pages 89-96, 1985. Google Scholar
  12. Kathrin Klamroth, Bruno Lang, and Michael Stiglmayr. Efficient dominance filtering for unions and minkowski sums of non-dominated sets. Available at SSRN 4308273, 2022. Google Scholar
  13. Jinfei Liu, Li Xiong, and Xiaofeng Xu. Faster output-sensitive skyline computation algorithm. Information Processing Letters, 114(12):710-713, 2014. Google Scholar
  14. Thibaut Lust and Daniel Tuyttens. Variable and large neighborhood search to solve the multiobjective set covering problem. Journal of Heuristics, 20:165-188, 2014. Google Scholar
  15. de Berg Mark, Cheong Otfried, van Kreveld Marc, and Overmars Mark. Computational geometry algorithms and applications. Spinger, 2008. Google Scholar
  16. Britta Schulze, Kathrin Klamroth, and Michael Stiglmayr. Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions. Journal of Global Optimization, 74(3):495-522, 2019. Google Scholar
  17. Sabine Storandt. Route planning for bicycles—exact constrained shortest paths made practical via contraction hierarchy. In Twenty-second international conference on automated planning and scheduling, 2012. Google Scholar
  18. Chih-Chiang Yu, Wing-Kai Hon, and Biing-Feng Wang. Improved data structures for the orthogonal range successor problem. Computational Geometry, 44(3):148-159, 2011. Google Scholar
  19. Han Zhang, Oren Salzman, Ariel Felner, TK Satish Kumar, Carlos Hernández Ulloa, and Sven Koenig. Efficient multi-query bi-objective search via contraction hierarchies. In Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS), 2023. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact