1 citations · 1 across the 2 of their papers we have counts for
5 papers
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
Vincent Cohen-Addad, Éric Colin de Verdière, Daniel Marx +1
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded gra…
Approximation Schemes for Capacitated Clustering in Doubling Metrics
Vincent Cohen-Addad
Motivated by applications in redistricting, we consider the uniform capacitated k-median and uniform capacitated k-means problems in bounded doubling metrics. We provide the first…
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 on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even i…
A Fast Approximation Scheme for Low-Dimensional -Means
Vincent Cohen-Addad
We consider the popular -means problem in -dimensional Euclidean space. Recently Friggstad, Rezapour, Salavatipour [FOCS'16] and Cohen-Addad, Klein, Mathieu [FOCS'16] showed…
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
Vincent Cohen-Addad, Arnaud de Mesmay
Given a graph cellularly embedded on a surface of genus , a cut graph is a subgraph of such that cutting along yields a topological disk. We provide a fixed…