Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CLUSTERING:
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 >>>

ISSN 1433-8092 | Imprint