3 papers
cs.DS2025
An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the -Means Problem
Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian
In this paper, we present an efficient massively parallel approximation algorithm for the -means problem. Specifically, we provide an MPC algorithm that computes a constant-fact…
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…