Funke Daniel, Hespe Demian, Sanders Peter, Storandt Sabine, Truschel Carina
KIT, Am Fasanengarten, Karlsruhe, 76128 Germany.
University of Konstanz, Universitätsstraße, Konstanz, 78464 Germany.
Algorithmica. 2025;87(8):1111-1144. doi: 10.1007/s00453-025-01314-y. Epub 2025 Apr 28.
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 , of size . The Pareto sum contains all non-dominated points of the Minkowski sum . Since the Minkowski sum has a size of , but the Pareto sum can be much smaller, the goal is to compute without having to compute and store all of . We present several new algorithms for efficient Pareto sum computation, including an output-sensitive successive algorithm with a running time of and a space consumption of for . If the elements of are streamed, the space consumption reduces to . For output sizes , we prove a conditional lower bound for Pareto sum computation, which excludes running times in for unless the (min,+)-convolution hardness conjecture fails. The successive algorithm matches this lower bound for . However, for , 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 , which matches the lower bound up to a logarithmic factor even for large . 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 .
在双目标优化问题中，目标通常是计算帕累托最优解集。针对这类问题的许多算法都依赖于部分解的高效合并或组合以及对所得集合中被支配解的过滤。在本文中，我们考虑计算两个给定规模为 的帕累托集的帕累托和的任务。帕累托和 包含闵可夫斯基和 的所有非支配点。由于闵可夫斯基和的规模为 ，但帕累托和 可能小得多，目标是在不必计算和存储所有 的情况下计算 。我们提出了几种用于高效帕累托和计算的新算法，包括一种输出敏感的逐次算法，其运行时间为 ，对于 空间消耗为 。如果 中的元素是流式输入的，空间消耗可降至 。对于输出规模 ，我们证明了帕累托和计算的条件下界，除非（最小，加）卷积硬度猜想不成立，否则排除运行时间在 内的情况。逐次算法对于 与该下界匹配。然而，对于 ，逐次算法呈现三次方运行时间。但我们还提出了一种算法，其空间消耗对输出敏感且运行时间为 ，即使对于大的 ，该算法在对数因子范围内与下界匹配。此外，我们描述了合适的工程技术来改善我们算法的实际运行时间。最后，我们对生成数据和真实世界数据进行了广泛的比较实验研究。作为一个展示应用，我们考虑道路网络中基于预处理的双目标路线规划。帕累托和计算是预处理阶段和查询阶段的瓶颈任务。我们表明，与完全存储 的算法相比，使用我们具有输出敏感空间消耗的算法能够处理更大的实例，并减少预处理和查询时间。
