5 citations · 9 across the 5 of their papers we have counts for
9 papers
Faster Sublinear-Time Edit Distance
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation al…
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution
Karl Bringmann, Alejandro Cassis
We revisit the classic 0-1-Knapsack problem, in which we are given items with their weights and profits as well as a weight budget , and the goal is to find a subset of item…
Optimal Algorithms for Bounded Weighted Edit Distance
Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic…
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
Karl Bringmann, Alejandro Cassis, Nick Fischer
In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wu…
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
Karl Bringmann, Alejandro Cassis
We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time $\w…
Improved Sublinear-Time Edit Distance for Preprocessed Strings
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rub…
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…
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We revisit the task of computing the edit distance in sublinear time. In the -gap edit distance problem the task is to distinguish whether the edit distance of two strings i…
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…