Pareto Sums of Pareto Sets: Lower Bounds and Algorithms

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 <i>A</i>, <i>B</i> of size <i>n</i>. The Pareto sum <i>C</i> contains all non-dominated points of the Minkowski sum <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mi>a</mml:mi> <mml:mo>+</mml:mo> <mml:mi>b</mml:mi> <mml:mo>|</mml:mo> <mml:mi>a</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>b</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>B</mml:mi> <mml:mo>}</mml:mo></mml:mrow> </mml:math> . Since the Minkowski sum has a size of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi> <mml:mn>2</mml:mn></mml:msup> </mml:math> , but the Pareto sum <i>C</i> can be much smaller, the goal is to compute <i>C</i> without having to compute and store all of <i>M</i>. We present several new algorithms for efficient Pareto sum computation, including an output-sensitive successive algorithm with a running time of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> and a space consumption of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mo>|</mml:mo> <mml:mi>C</mml:mi> <mml:mo>|</mml:mo></mml:mrow> </mml:math> . If the elements of <i>C</i> are streamed, the space consumption reduces to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> . For output sizes <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi></mml:mrow> </mml:math> , we prove a conditional lower bound for Pareto sum computation, which excludes running times in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup><mml:mi>n</mml:mi> <mml:mrow><mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:mi>δ</mml:mi></mml:mrow> </mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:math> for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>δ</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn></mml:mrow> </mml:math> unless the (min,+)-convolution hardness conjecture fails. The successive algorithm matches this lower bound for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> . However, for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup><mml:mi>n</mml:mi> <mml:mn>2</mml:mn></mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:math> , 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup><mml:mi>n</mml:mi> <mml:mn>2</mml:mn></mml:msup> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> , which matches the lower bound up to a logarithmic factor even for large <i>k</i>. 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 <i>M</i>.