Vincent Cohen-Addad

activity

20152026

most citedFast and Compact Exact Distance Oracle for Planar Graphs

7 citations · 9 across the 8 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

cs.DS2017

The Bane of Low-Dimensionality Clustering

Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg +1

In this paper, we give a conditional lower bound of $n^{Ω (k)}$ on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even i…

cs.DS2017★ 1 cited

A Fast Approximation Scheme for Low-Dimensional $k$ -Means

Vincent Cohen-Addad

We consider the popular $k$ -means problem in $d$ -dimensional Euclidean space. Recently Friggstad, Rezapour, Salavatipour [FOCS'16] and Cohen-Addad, Klein, Mathieu [FOCS'16] showed…

cs.DS2017★ 7 cited

Fast and Compact Exact Distance Oracle for Planar Graphs

Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen

For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an $O (n^{5/3})$ -space distance oracle which answers…

The Bane of Low-Dimensionality Clustering

A Fast Approximation Scheme for Low-Dimensional k-Means

Fast and Compact Exact Distance Oracle for Planar Graphs

A Fast Approximation Scheme for Low-Dimensional $k$ -Means