4 papers
Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution
Geri Gokaj, Marvin Künnemann, Sabine Storandt +1
The Pareto sum of two-dimensional point sets and in is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the…
Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
Sebastian Angrick, Kevin Buchin, Geri Gokaj +1
To measure the shape similarity of point sets, various notions of the Hausdorff distance under translation are widely studied. In this context, for an -point set and -poi…
Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
Nick Fischer, Marvin Künnemann, Mirza Redzic
We revisit the classic Maximum -Coverage problem: Determine the largest number of elements that can be covered by choosing sets from a given family $\mathcal{F} = \{S_1,…
Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
Geri Gokaj, Marvin Künnemann
In the last three decades, the -SUM hypothesis has emerged as a satisfying explanation of long-standing time barriers for a variety of algorithmic problems. Yet to this day, the…