2 papers
cs.DS2021
A Linear-Time -Approximation for Longest Common Subsequence
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length . While a simple quadratic algorithm has been known for the problem fo…
cs.CG2018
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann +5
We consider very natural "fence enclosure" problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set of points in th…