6 citations · 6 across the 5 of their papers we have counts for
8 papers · 1 filter
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk +1
We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph excluding a fixed-minor on vertices and an accuracy parameter $\varepsil…
Streaming Euclidean MST to a Constant Factor
Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram +2
We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an -point set .…
A Quasipolynomial -Approximation for Planar Sparsest Cut
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein +1
The (non-uniform) sparsest cut problem is the following graph-partitioning problem: given a "supply" graph, and demands on pairs of vertices, delete some subset of supply edges to…
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein +1
Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction sin…
On the computational tractability of a geographic clustering problem arising in redistricting
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx
Redistricting is the problem of dividing a state into a number of regions, called districts. Voters in each district elect a representative. The primary criteria are: each dist…
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
The Sparsest Cut is a fundamental optimization problem that has been extensively studied. For planar inputs the problem is in and can be solved in time if all…
Balanced power diagrams for redistricting
Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
We propose a method for redistricting, decomposing a geographical area into subareas, called districts, so that the populations of the districts are as close as possible and the di…
Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) -median and -mea…