
A New Coreset Framework for Clustering
Given a metric space, the (k,z)clustering problem consists of finding k...
read it

Fast and Accurate kmeans++ via Rejection Sampling
kmeans++ <cit.> is a widely used clustering algorithm that is easy to i...
read it

On Approximability of Clustering Problems Without Candidate Centers
The kmeans objective is arguably the most widelyused cost function for...
read it

On Light Spanners, Lowtreewidth Embeddings and Efficient Traversing in Minorfree Graphs
Understanding the structure of minorfree metrics, namely shortest path ...
read it

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...
read it

On Efficient Low Distortion Ultrametric Embedding
A classic problem in unsupervised learning and data analysis is to find ...
read it

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...
read it

Online kmeans Clustering
We study the problem of online clustering where a clustering algorithm h...
read it

Efficient approximation schemes for uniformcost clustering problems in planar graphs
We consider the kMedian problem on planar graphs: given an edgeweighte...
read it

Tight FPT Approximations for kMedian and kMeans
We investigate the finegrained complexity of approximating the classica...
read it

A PolynomialTime Approximation Scheme for Facility Location on Planar Graphs
We consider the classic Facility Location problem on planar graphs (non...
read it

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
We prove essentially tight lower bounds, conditionally to the Exponentia...
read it

Lower bounds for text indexing with mismatches and differences
In this paper we study lower bounds for the fundamental problem of text ...
read it

NearLinear Time Approximation Schemes for Clustering in Doubling Metrics
We consider the classic Facility Location, kMedian, and kMeans problem...
read it

Approximation Schemes for Capacitated Clustering in Doubling Metrics
Motivated by applications in redistricting, we consider the uniform capa...
read it

InstanceOptimality in the Noisy Valueand ComparisonModel  Accept, Accept, Strong Accept: Which Papers get in?
Motivated by crowdsourced computation, peergrading, and recommendation ...
read it

Fast Fencing
We consider very natural "fence enclosure" problems studied by Capoyleas...
read it

The Bane of LowDimensionality Clustering
In this paper, we give a conditional lower bound of n^Ω(k) on running ti...
read it

A Fast Approximation Scheme for LowDimensional kMeans
We consider the popular kmeans problem in ddimensional Euclidean space...
read it

Online Optimization of Smoothed Piecewise Constant Functions
We study online optimization of smoothed piecewise constant functions ov...
read it
Vincent CohenAddad
is this you? claim profile