Vincent Cohen-Addad

research

∙ 04/14/2023

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1

We prove that there is a randomized polynomial-time algorithm that given...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 01/31/2023

Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees

Hierarchical Clustering is a popular unsupervised machine learning metho...

0 Jacob Imola, et al. ∙

research

∙ 01/11/2023

Private estimation algorithms for stochastic block models and mixture models

We introduce general tools for designing efficient private estimation al...

0 Hongjie Chen, et al. ∙

research

∙ 12/29/2022

Graph Searching with Predictions

Consider an agent exploring an unknown graph in search of some goal stat...

0 Siddhartha Banerjee, et al. ∙

research

∙ 12/13/2022

Streaming Euclidean MST to a Constant Factor

We study streaming algorithms for the fundamental geometric problem of c...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 11/15/2022

Improved Coresets for Euclidean k-Means

Given a set of n points in d dimensions, the Euclidean k-means problem (...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 09/05/2022

The Power of Uniform Sampling for Coresets

Motivated by practical generalizations of the classic k-median and k-mea...

0 Vladimir Braverman, et al. ∙

research

∙ 08/30/2022

On the Fixed-Parameter Tractability of Capacitated Clustering

We study the complexity of the classic capacitated k-median and k-means ...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 08/29/2022

Fitting Metrics and Ultrametrics with Minimum Disagreements

Given x ∈ (ℝ_≥ 0)^[n]2 recording pairwise distances, the METRIC VIOLATIO...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 07/22/2022

Correlation Clustering with Sherali-Adams

Given a complete graph G = (V, E) where each edge is labeled + or -, the...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 07/11/2022

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median

The Uncapacitated Facility Location (UFL) problem is one of the most fun...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 06/17/2022

Scalable Differentially Private Clustering via Hierarchically Separated Trees

We study the private k-median and k-means clustering problem in d dimens...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 05/24/2022

Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy

Among the various aspects of algorithmic fairness studied in recent year...

0 Limor Gultchin, et al. ∙

research

∙ 04/11/2022

Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets

Motivated by data analysis and machine learning applications, we conside...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 03/03/2022

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

We study several questions related to diversifying search results. We gi...

0 Amir Abboud, et al. ∙

research

∙ 03/02/2022

Near-Optimal Correlation Clustering with Privacy

Correlation clustering is a central problem in unsupervised learning, wi...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 02/25/2022

Towards Optimal Lower Bounds for k-median and k-means Coresets

Given a set of points in a metric space, the (k,z)-clustering problem co...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 12/06/2021

On Complexity of 1-Center in Various Metrics

We consider the classic 1-center problem: Given a set P of n points in a...

0 Amir Abboud, et al. ∙

research

∙ 11/21/2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics

K-median and k-means are the two most popular objectives for clustering ...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 11/11/2021

A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time

In the non-uniform sparsest cut problem, we are given a supply graph G a...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 11/08/2021

An Improved Local Search Algorithm for k-Median

We present a new local-search algorithm for the k-median clustering prob...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 10/06/2021

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

We consider the numerical taxonomy problem of fitting a positive distanc...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 06/15/2021

Correlation Clustering in Constant Many Parallel Rounds

Correlation clustering is a central topic in unsupervised learning, with...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 06/15/2021

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

We consider the classic problem of computing the Longest Common Subseque...

0 Karl Bringmann, et al. ∙

research

∙ 05/31/2021

A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut

The (non-uniform) sparsest cut problem is the following graph-partitioni...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 04/13/2021

A New Coreset Framework for Clustering

Given a metric space, the (k,z)-clustering problem consists of finding k...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 12/22/2020

Fast and Accurate k-means++ via Rejection Sampling

k-means++ <cit.> is a widely used clustering algorithm that is easy to i...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 09/30/2020

On Approximability of Clustering Problems Without Candidate Centers

The k-means objective is arguably the most widely-used cost function for...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 09/10/2020

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

Understanding the structure of minor-free metrics, namely shortest path ...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 09/01/2020

On the computational tractability of a geographic clustering problem arising in redistricting

Redistricting is the problem of dividing a state into a number k of regi...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 08/15/2020

On Efficient Low Distortion Ultrametric Embedding

A classic problem in unsupervised learning and data analysis is to find ...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 07/05/2020

New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut

The Sparsest Cut is a fundamental optimization problem that has been ext...

0 Amir Abboud, et al. ∙

research

∙ 09/15/2019

Online k-means Clustering

We study the problem of online clustering where a clustering algorithm h...

6 Vincent Cohen-Addad, et al. ∙

research

∙ 05/02/2019

Efficient approximation schemes for uniform-cost clustering problems in planar graphs

We consider the k-Median problem on planar graphs: given an edge-weighte...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 04/28/2019

Tight FPT Approximations for k-Median and k-Means

We investigate the fine-grained complexity of approximating the classica...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 04/24/2019

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs

We consider the classic Facility Location problem on planar graphs (non-...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 03/20/2019

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

We prove essentially tight lower bounds, conditionally to the Exponentia...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 12/21/2018

Lower bounds for text indexing with mismatches and differences

In this paper we study lower bounds for the fundamental problem of text ...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 12/20/2018

Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics

We consider the classic Facility Location, k-Median, and k-Means problem...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 12/19/2018

Approximation Schemes for Capacitated Clustering in Doubling Metrics

Motivated by applications in redistricting, we consider the uniform capa...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 06/21/2018

Instance-Optimality in the Noisy Value-and Comparison-Model --- Accept, Accept, Strong Accept: Which Papers get in?

Motivated by crowdsourced computation, peer-grading, and recommendation ...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 03/31/2018

Fast Fencing

We consider very natural "fence enclosure" problems studied by Capoyleas...

0 Mikkel Abrahamsen, et al. ∙

research

∙ 11/03/2017

The Bane of Low-Dimensionality Clustering

In this paper, we give a conditional lower bound of n^Ω(k) on running ti...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 08/24/2017

A Fast Approximation Scheme for Low-Dimensional k-Means

We consider the popular k-means problem in d-dimensional Euclidean space...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 04/07/2016

Online Optimization of Smoothed Piecewise Constant Functions

We study online optimization of smoothed piecewise constant functions ov...

0 Vincent Cohen-Addad, et al. ∙

Vincent Cohen-Addad

Featured Co-authors