research
∙
05/11/2023
Optimal Algorithms for Bounded Weighted Edit Distance
The edit distance of two strings is the minimum number of insertions, de...
share
research
∙
05/02/2023
Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution
We revisit the classic 0-1-Knapsack problem, in which we are given n ite...
research
∙
04/11/2023
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
In this work we revisit the fundamental Single-Source Shortest Paths (SS...
research
∙
05/17/2022
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
We present new exact and approximation algorithms for 0-1-Knapsack and U...
research
∙
04/29/2022
Improved Sublinear-Time Edit Distance for Preprocessed Strings
We study the problem of approximating the edit distance of two strings i...
research
∙
04/25/2022
A Structural Investigation of the Approximability of Polynomial-Time Problems
We initiate the systematic study of a recently introduced polynomial-tim...
research
∙
02/16/2022
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
We revisit the task of computing the edit distance in sublinear time. In...
research
∙
07/04/2021