96 citations · 442 across the 64 of their papers we have counts for
6 papers · 2 filters
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…
Approximating Subset Sum Ratio faster than Subset Sum
Karl Bringmann
Subset Sum Ratio is the following optimization problem: Given a set of positive numbers , find disjoint subsets minimizing the ratio $\max\{Σ(X)/Σ(Y),Σ(Y)/…
The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer +1
What is the time complexity of matrix multiplication of sparse integer matrices with nonzeros in the input and nonzeros in the output? This paper provides improv…
Knapsack with Small Items in Near-Quadratic Time
Karl Bringmann
The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research w…
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…
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…