On variants of k-means clustering

DOI10.4230/LIPICS.SOCG.2016.14MaRDI QIDQ3132847zbMATH OpenFDO

Authors Sayan Bandyapadhyay, Kasturi Varadarajan

Publication date 30 January 2018

Full work available at URL https://arxiv.org/abs/1512.02985

zbMATH Keywords

\(k\)-meanslocal searchfacility locationgeometric approximation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Local search yields a PTAS for \(k\)-means in doubling metrics
• A local search approximation algorithm for \(k\)-means clustering
• A local search approximation algorithm for \(k\)-means clustering
• A bi-criteria approximation algorithm for \(k\)-means
• Linear-time approximation schemes for clustering problems in any dimensions

Cited in

(38)

• A PTAS for k-means clustering based on weak coresets
• Clustering methods based on variational analysis in the space of measures.
• Degrees of freedom and model selection for \(k\)-means clustering
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• On the Consistency of k-means++ algorithm
• A PTAS for the \(k\)-consensus structures problem under squared Euclidean distance
• A local search approximation algorithm for \(k\)-means clustering
• Variance-based cluster selection criteria in a \(K\)-means framework for one-mode dissimilarity data
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Local search approximation algorithms for the \(k\)-means problem with penalties
• Improved Conic Reformulations for $K$-means Clustering
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• A survey on theory and algorithms for \(k\)-means problems
• Bi-criteria linear-time approximations for generalized k-mean/median/center
• scientific article; zbMATH DE number 2222601 (Why is no real title available?)
• scientific article; zbMATH DE number 5695636 (Why is no real title available?)
• Good (K-means) clusterings are unique (up to small perturbations)
• A local search approximation algorithm for \(k\)-means clustering
• Two Modifications of Yinyang K-means Algorithm
• Lossy kernelization of same-size clustering
• A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems
• Lossy kernelization of same-size clustering
• scientific article; zbMATH DE number 5235996 (Why is no real title available?)
• The hardness of approximation of Euclidean \(k\)-means
• Some refinements of rough \(k\)-means clustering
• scientific article; zbMATH DE number 2170297 (Why is no real title available?)
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• A survey on algorithms for \(k\)-means problem and its variants
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• A PTAS for the k-Consensus Structures Problem Under Euclidean Squared Distance
• Local search approximation algorithms for the sum of squares facility location problems
• Some Notes on K-Harmonic Means Clustering Algorithm
• Optimising \(k\)-means clustering results with standard software packages
• A bi-criteria approximation algorithm for \(k\)-means
• Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• On the quality of \(k\)-means clustering based on grouped data
• \(K\)-means cloning: adaptive spherical \(K\)-means clustering

This page was built for publication: On variants of \(k\)-means clustering

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