{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:39:05Z","timestamp":1759847945912,"version":"3.44.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["882500"],"award-info":[{"award-number":["882500"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["251654672 \u2013 TRR 161"],"award-info":[{"award-number":["251654672 \u2013 TRR 161"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010583","name":"Universit\u00e4t Konstanz","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010583","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,8]]},"abstract":"Abstract<\/jats:title>\n 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 article, we consider the task of computing the Pareto sum of two given Pareto sets A<\/jats:italic>,\u00a0B<\/jats:italic> of size n<\/jats:italic>. The Pareto sum C<\/jats:italic> contains all non-dominated points of the Minkowski sum \n \n $$M = \\{a+b|a \\in A, b\\in B\\}$$<\/jats:tex-math>\n \n \n M<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n a<\/mml:mi>\n +<\/mml:mo>\n b<\/mml:mi>\n |<\/mml:mo>\n a<\/mml:mi>\n \u2208<\/mml:mo>\n A<\/mml:mi>\n ,<\/mml:mo>\n b<\/mml:mi>\n \u2208<\/mml:mo>\n B<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Since the Minkowski sum has a size of \n \n $$n^2$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, but the Pareto sum C<\/jats:italic> can be much smaller, the goal is to compute C<\/jats:italic> without having to compute and store all of M<\/jats:italic>. We present several new algorithms for efficient Pareto sum computation, including an output-sensitive successive algorithm with a running time of \n \n $$\\mathcal {O}(n \\log n + nk)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n n<\/mml:mi>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and a space consumption of \n \n $$\\mathcal {O}(n+k)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for \n \n $$k=|C|$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n =<\/mml:mo>\n |<\/mml:mo>\n C<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. If the elements of C<\/jats:italic> are streamed, the space consumption reduces to \n \n $$\\mathcal {O}(n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. For output sizes \n \n $$k \\ge 2n$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, we prove a conditional lower bound for Pareto sum computation, which excludes running times in \n \n $$\\mathcal {O}(n^{2-\\delta })$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 2<\/mml:mn>\n -<\/mml:mo>\n \u03b4<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for \n \n $$\\delta > 0$$<\/jats:tex-math>\n \n \n \u03b4<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> unless the (min,+)-convolution hardness conjecture fails. The successive algorithm matches this lower bound for \n \n $$k \\in \\Theta (n)$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2208<\/mml:mo>\n \u0398<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. However, for \n \n $$k \\in \\Theta (n^2)$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2208<\/mml:mo>\n \u0398<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, the successive algorithm exhibits a cubic running time. But we also present an algorithm with an output-sensitive space consumption and a running time of \n \n $$\\mathcal {O}(n^2 \\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, which matches the lower bound up to a logarithmic factor even for large k<\/jats:italic>. Furthermore, we describe suitable engineering techniques to improve the practical running times of our algorithms. Finally, we provide an extensive comparative experimental study on generated and real-world data. As a showcase application, we consider preprocessing-based bi-criteria route planning in road networks. Pareto sum computation is the bottleneck task in the preprocessing phase and in the query phase. We show that using our algorithms with an output-sensitive space consumption allows to tackle larger instances and reduces the preprocessing and query time compared to algorithms that fully store M<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00453-025-01314-y","type":"journal-article","created":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:17:53Z","timestamp":1745799473000},"page":"1111-1144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Pareto Sums of Pareto Sets: Lower Bounds and Algorithms"],"prefix":"10.1007","volume":"87","author":[{"given":"Daniel","family":"Funke","sequence":"first","affiliation":[]},{"given":"Demian","family":"Hespe","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[]},{"given":"Sabine","family":"Storandt","sequence":"additional","affiliation":[]},{"given":"Carina","family":"Truschel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,28]]},"reference":[{"issue":"3","key":"1314_CR1","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s10898-019-00745-6","volume":"74","author":"B Schulze","year":"2019","unstructured":"Schulze, B., Klamroth, K., Stiglmayr, M.: Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions. J. Global Optim. 74(3), 495\u2013522 (2019)","journal-title":"J. Global Optim."},{"key":"1314_CR2","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s002910000046","volume":"22","author":"M Ehrgott","year":"2000","unstructured":"Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR-Spektrum 22, 425\u2013460 (2000)","journal-title":"OR-Spektrum"},{"key":"1314_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.trc.2012.08.003","volume":"27","author":"C Artigues","year":"2013","unstructured":"Artigues, C., Huguet, M.-J., Gueye, F., Schettini, F., Dezou, L.: State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths. Trans. Res. Part C Emerg. Technol. 27, 233\u2013259 (2013)","journal-title":"Trans. Res. Part C Emerg. Technol."},{"key":"1314_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10732-013-9236-8","volume":"20","author":"T Lust","year":"2014","unstructured":"Lust, T., Tuyttens, D.: Variable and large neighborhood search to solve the multiobjective set covering problem. J. Heuristics 20, 165\u2013188 (2014)","journal-title":"J. Heuristics"},{"key":"1314_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2023.106506","volume":"163","author":"K Klamroth","year":"2024","unstructured":"Klamroth, K., Lang, B., Stiglmayr, M.: Efficient dominance filtering for unions and Minkowski sums of non-dominated sets. Comput. Operat. Res. 163, 106506 (2024)","journal-title":"Comput. Operat. Res."},{"key":"1314_CR6","doi-asserted-by":"crossref","unstructured":"Erb, S., Kobitzsch, M., Sanders, P.: Parallel bi-objective shortest paths using weight-balanced B-trees with bulk updates. In: Experimental Algorithms: 13th International Symposium (SEA). Proceedings 13, pp. 111\u2013122 (2014)","DOI":"10.1007\/978-3-319-07959-2_10"},{"key":"1314_CR7","doi-asserted-by":"crossref","unstructured":"Ahmadi, S., Tack, G., Harabor, D.D., Kilby, P.: Bi-objective search with bi-directional A*. In: Proceedings of the International Symposium on Combinatorial Search, vol. 12, pp. 142\u2013144 (2021)","DOI":"10.1609\/socs.v12i1.18563"},{"key":"1314_CR8","doi-asserted-by":"crossref","unstructured":"Storandt, S.: Route planning for bicycles-exact constrained shortest paths made practical via contraction hierarchy. In: Twenty-second International Conference on Automated Planning and Scheduling, pp. 234\u2013242 (2012)","DOI":"10.1609\/icaps.v22i1.13495"},{"key":"1314_CR9","doi-asserted-by":"crossref","unstructured":"Zhang, H., Salzman, O., Felner, A., Kumar, T.S., Ulloa, C.H., Koenig, S.: Efficient multi-query bi-objective search via contraction hierarchies. In: Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS), pp. 452\u2013461 (2023)","DOI":"10.1609\/icaps.v33i1.27225"},{"key":"1314_CR10","doi-asserted-by":"crossref","unstructured":"Funke, S., Storandt, S.: Personalized route planning in road networks. In: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 1\u201310 (2015)","DOI":"10.1145\/2820783.2820830"},{"issue":"1\u20132","key":"1314_CR11","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.comgeo.2011.08.001","volume":"45","author":"W-M Chen","year":"2012","unstructured":"Chen, W.-M., Hwang, H.-K., Tsai, T.-H.: Maxima-finding algorithms for multidimensional samples: A two-phase approach. Comput. Geom. 45(1\u20132), 33\u201353 (2012)","journal-title":"Comput. Geom."},{"key":"1314_CR12","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G., Seidel, R.: Output-size sensitive algorithms for finding maximal vectors. In: Proceedings of the First Annual Symposium on Computational Geometry, pp. 89\u201396 (1985)","DOI":"10.1145\/323233.323246"},{"key":"1314_CR13","unstructured":"Berg, M., Cheong, O., Kreveld, M.J., Overmars, M.H.: Computational geometry: algorithms and applications, 3rd edition (2008)"},{"issue":"1\u20132","key":"1314_CR14","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0925-7721(01)00041-4","volume":"21","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom. 21(1\u20132), 39\u201361 (2002)","journal-title":"Comput. Geom."},{"key":"1314_CR15","doi-asserted-by":"crossref","unstructured":"Kerb\u00e9r\u00e9n\u00e8s, A., Vanderpooten, D., Vanpeperstraete, J.-M.: Computing efficiently the nondominated subset of a set sum. International Transactions in Operational Research, 3455\u20133478 (2022)","DOI":"10.1111\/itor.13191"},{"key":"1314_CR16","doi-asserted-by":"crossref","unstructured":"Shu, T., Nan, Y., Shang, K., Ishibuchi, H.: Two-phase procedure for efficiently removing dominated solutions from large solution sets. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 740\u2013748 (2023)","DOI":"10.1145\/3583131.3590404"},{"key":"1314_CR17","doi-asserted-by":"crossref","unstructured":"Preparata, F.P., Shamos, M.I.: Computational geometry - an introduction (1985)","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"1314_CR18","doi-asserted-by":"crossref","unstructured":"Gomes-Selman, J.M., Shi, Q., Xue, Y., Garcia-Villacorta, R., Flecker, A.S., Gomes, C.P.: Boosting efficiency for computing the Pareto frontier on tree structured networks. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR). Proceedings 15, pp. 263\u2013279 (2018)","DOI":"10.1007\/978-3-319-93031-2_19"},{"issue":"1","key":"1314_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3293465","volume":"15","author":"M Cygan","year":"2019","unstructured":"Cygan, M., Mucha, M., Wegrzycki, K., Wlodarczyk, M.: On problems equivalent to (min,+)-convolution. ACM Trans. Algorithms (TALG) 15(1), 1\u201325 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"5","key":"1314_CR20","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","volume":"9","author":"AM Andrew","year":"1979","unstructured":"Andrew, A.M.: Another efficient algorithm for convex hulls in two dimensions. Inf. Process. Lett. 9(5), 216\u2013219 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"1314_CR21","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1109\/TEVC.2018.2799684","volume":"22","author":"A Jaszkiewicz","year":"2018","unstructured":"Jaszkiewicz, A., Lust, T.: ND-tree-based update: a fast algorithm for the dynamic nondominance problem. IEEE Trans. Evol. Comput. 22(5), 778\u2013791 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"5","key":"1314_CR22","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1109\/TEVC.2022.3145631","volume":"26","author":"B Lang","year":"2022","unstructured":"Lang, B.: Space-partitioned ND-trees for the dynamic nondominance problem. IEEE Trans. Evol. Comput. 26(5), 1004\u20131014 (2022)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"12","key":"1314_CR23","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1016\/j.ipl.2014.06.014","volume":"114","author":"J Liu","year":"2014","unstructured":"Liu, J., Xiong, L., Xu, X.: Faster output-sensitive skyline computation algorithm. Inf. Process. Lett. 114(12), 710\u2013713 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1314_CR24","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.comgeo.2010.09.001","volume":"44","author":"C-C Yu","year":"2011","unstructured":"Yu, C.-C., Hon, W.-K., Wang, B.-F.: Improved data structures for the orthogonal range successor problem. Comput. Geom. 44(3), 148\u2013159 (2011)","journal-title":"Comput. Geom."},{"key":"1314_CR25","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: A data structuring technique with geometric applications. In: International Colloquium on Automata, Languages, and Programming, pp. 90\u2013100 (1985)","DOI":"10.1007\/BFb0015734"},{"issue":"4","key":"1314_CR26","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1145\/322092.322095","volume":"25","author":"JL Bentley","year":"1978","unstructured":"Bentley, J.L., Kung, H.-T., Schkolnick, M., Thompson, C.D.: On the average number of maxima in a set of vectors and applications. J. ACM (JACM) 25(4), 536\u2013543 (1978)","journal-title":"J. ACM (JACM)"},{"issue":"3","key":"1314_CR27","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1214\/aoap\/1028903455","volume":"8","author":"Z-D Bai","year":"1998","unstructured":"Bai, Z.-D., Chao, C.-C., Hwang, H.-K., Liang, W.-Q.: On the variance of the number of maxima in random vectors and its applications. Ann. Appl. Probab. 8(3), 886\u2013895 (1998)","journal-title":"Ann. Appl. Probab."},{"issue":"4","key":"1314_CR28","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H-T Kung","year":"1975","unstructured":"Kung, H.-T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM (JACM) 22(4), 469\u2013476 (1975)","journal-title":"J. ACM (JACM)"},{"key":"1314_CR29","doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. In: 33rd ACM Symposium on Theory of Computing, pp. 296\u2013305 (2001)","DOI":"10.1145\/380752.380813"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01314-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01314-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01314-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T12:19:21Z","timestamp":1757161161000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01314-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":29,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["1314"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01314-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"28 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}