Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Clustering:
TR02-025 | 26th April 2002
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

We give polynomial time approximation schemes for the problem
of partitioning an input set of n points into a fixed number
k of clusters so as to minimize the sum over all clusters of
the total pairwise distances in a cluster. Our algorithms work
for arbitrary metric spaces as well ... more >>>

TR04-010 | 26th January 2004
Michal Parnas, Dana Ron, Ronitt Rubinfeld

Tolerant Property Testing and Distance Approximation

A standard property testing algorithm is required to determine
with high probability whether a given object has property
P or whether it is \epsilon-far from having P, for any given
distance parameter \epsilon. An object is said to be \epsilon-far
from having ... more >>>

TR04-050 | 13th June 2004
Michelle Effros, Leonard Schulman

Deterministic clustering with data nets

We consider the $K$-clustering problem with the $\ell_2^2$
distortion measure, also known as the problem of optimal
fixed-rate vector quantizer design. We provide a deterministic
approximation algorithm which works for all dimensions $d$ and
which, given a data set of size $n$, computes in time
more >>>

TR04-058 | 28th May 2004
John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

Identifying Clusters from Positive Data

The present work studies clustering from an abstract point of view
and investigates its properties in the framework of inductive inference.
Any class $S$ considered is given by a numbering
$A_0,A_1,...$ of nonempty subsets of the natural numbers
or the rational k-dimensional vector space as a hypothesis space.
A clustering ... more >>>

TR11-015 | 8th December 2010
Marcel R. Ackermann, Johannes Blömer, Christoph Scholz

Hardness and Non-Approximability of Bregman Clustering Problems

We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman ... more >>>

TR13-031 | 22nd February 2013
Irit Dinur, Elazar Goldenberg

Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.

In ... more >>>

TR21-177 | 22nd November 2021
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics

k-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, particularly in $\ell_p$-metrics, remains a major open problem. In this paper, we significantly improve upon the hardness of approximation factors known in literature for these objectives ... more >>>

ISSN 1433-8092 | Imprint