28 citations · 32 across the 5 of their papers we have counts for
11 papers
A Structural Investigation of the Approximability of Polynomial-Time Problems
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest…
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves in , it provides a ro…
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union
Marvin Künnemann, André Nusser
We revisit the classical problem of determining the largest copy of a simple polygon that can be placed into a simple polygon . Despite significant effort, known algorithms…
Fine-Grained Completeness for Optimization in P
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for dec…
Impossibility Results for Grammar-Compressed Linear Algebra
Amir Abboud, Arturs Backurs, Karl Bringmann +1
To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size down to size , it certainly makes it ea…
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
Karl Bringmann, Marvin Künnemann, André Nusser
Consider the natural question of how to measure the similarity of curves in the plane by a quantity that is invariant under translations of the curves. Such a measure is justified…