7 citations · 9 across the 8 of their papers we have counts for
10 papers
A Strong Linear Programming Relaxation for Weighted Tree Augmentation
Vincent Cohen-Addad, Marina Drygala, Nathan Klein +1
The Weighted Tree Augmentation Problem (WTAP) is a fundamental network design problem where the goal is to find a minimum-cost set of additional edges (links) to make an input tree…
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar
We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC'12], where, given a random bipartite graph with edges and an unknown bipartition $(A…
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time
Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ra…
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…
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 -space distance oracle which answers…
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals
Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
For an undirected edge-weighted graph and a set of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from disconn…
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…