5 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…
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction
Marvin Künnemann, Dániel Marx
To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean con…