Vincent Cohen-Addad

activity

20182025

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2025

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$ -Means Problem

Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian

In this paper, we present an efficient massively parallel approximation algorithm for the $k$ -means problem. Specifically, we provide an MPC algorithm that computes a constant-fact…

cs.DS2021

A Linear-Time $n^{0.4}$ -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 $n$ . While a simple quadratic algorithm has been known for the problem fo…

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the k-Means Problem

A Linear-Time n0.4-Approximation for Longest Common Subsequence

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$ -Means Problem

A Linear-Time $n^{0.4}$ -Approximation for Longest Common Subsequence