5 citations · 9 across the 5 of their papers we have counts for
4 papers · 1 filter
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…