Efficient approximation algorithms for clustering point-sets

DOI10.1016/J.COMGEO.2007.12.002MaRDI QIDQ733558zbMATH OpenOpenAlexFDO

Authors Guang Xu, Jinhui Xu

Publication date 16 October 2009

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2007.12.002

zbMATH Keywords

core-setsk-center clusteringk-median clustering

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

As is well known, cluster analysis or clustering is the assignment of a set of observations, listed as points is some space, into subsets (called clusters) so that observations in the same cluster are similar in some sense. The authors address the new problem of clustering not a set of points but a set of \(n\) finite point sets. So, the point sets clustering problem requires that all points in a single point set be clustered into the same cluster. The main problem with this kind of requirement is that the metric properties of the underlying distance function are no longer valid. Nevertheless, the authors are still able to give algorithms for the \(k\)-center clustering problem on point sets and for the \(k\)-median problem.

Recommendations

• Approximation schemes for clustering problems
• Exact and approximation algorithms for clustering
• On approximate geometric \(k\)-clustering
• Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space
• scientific article; zbMATH DE number 1303609

Cites work

• Algorithms for coloring quadtrees
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Approximate clustering via core-sets
• Approximation algorithms for a \(k\)-line center
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for NP-hard problems.
• Clustering to minimize the maximum intercluster distance
• scientific article; zbMATH DE number 1303609 (Why is no real title available?)
• scientific article; zbMATH DE number 2079414 (Why is no real title available?)
• scientific article; zbMATH DE number 6472586 (Why is no real title available?)
• On coresets for k-means and k-median clustering
• Pattern classification.
• Reductions among high dimensional proximity problems

Cited in

(13)

• Exact and approximation algorithms for clustering
• Preclustering algorithms for imprecise points
• A unified framework for clustering constrained data without locality property
• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• Point clustering via voting maximization
• $k$-median clustering under discrete Fréchet and Hausdorff distances
• On Finding the Jaccard Center
• Approximate range queries for clustering
• Active clustering of biological sequences
• scientific article; zbMATH DE number 7053357 (Why is no real title available?)
• Preclustering Algorithms for Imprecise Points
• Improved separated red-blue center clustering
• Clustering point sets revisited

This page was built for publication: Efficient approximation algorithms for clustering point-sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733558)