7 citations · 14 across the 5 of their papers we have counts for
6 papers · 1 filter
Sensitivity Sampling for -Means: Worst Case and Stability Optimal Coreset Bounds
Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu +2
Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as -means. Given a point set , a coreset is a small, weighted summ…
Towards Optimal Lower Bounds for k-median and k-means Coresets
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic +1
Given a set of points in a metric space, the -clustering problem consists of finding a set of points called centers, such that the sum of distances raised to the power o…
An Improved Local Search Algorithm for k-Median
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu +2
We present a new local-search algorithm for the -median clustering problem. We show that local optima for this algorithm give a -approximation; our result improves up…
Dominating Sets and Connected Dominating Sets in Dynamic Graphs
Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis +1
In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present…
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic
We consider the classic Facility Location, -Median, and -Means problems in metric spaces of doubling dimension . We give nearly linear-time approximation schemes for each…
Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Graphs with Bounded Highway Dimension
Amariah Becker, Philip N. Klein, David Saulpic
The concept of bounded highway dimension was developed to capture observed properties of the metrics of road networks. We show that a graph with bounded highway dimension, for any…