On variants of k-means clustering

DOI10.4230/LIPICS.SOCG.2016.14zbMATH Open1387.68235arXiv1512.02985MaRDI QIDQ3132847FDOQ3132847

Authors: Sayan Bandyapadhyay, Kasturi Varadarajan 

Publication date: 30 January 2018

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

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

zbMATH Keywords

\(k\)-meanslocal searchfacility locationgeometric approximation

Mathematics Subject Classification ID

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

Cited In (38)

• On the Consistency of k-means++ algorithm
• The hardness of approximation of Euclidean \(k\)-means
• Title not available (Why is that?)
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• Local search approximation algorithms for the sum of squares facility location problems
• Title not available (Why is that?)
• On the quality of \(k\)-means clustering based on grouped data
• Title not available (Why is that?)
• Optimising \(k\)-means clustering results with standard software packages
• 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
• A PTAS for k-means clustering based on weak coresets
• Local search approximation algorithms for the \(k\)-means problem with penalties
• A local search approximation algorithm for \(k\)-means clustering
• A PTAS for the k-Consensus Structures Problem Under Euclidean Squared Distance
• A bi-criteria approximation algorithm for \(k\)-means
• A PTAS for the \(k\)-consensus structures problem under squared Euclidean distance
• Good (K-means) clusterings are unique (up to small perturbations)
• Some refinements of rough \(k\)-means clustering
• Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• Bi-criteria linear-time approximations for generalized k-mean/median/center
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• \(K\)-means cloning: adaptive spherical \(K\)-means clustering
• Clustering methods based on variational analysis in the space of measures.
• A local search approximation algorithm for \(k\)-means clustering
• Title not available (Why is that?)
• A survey on algorithms for \(k\)-means problem and its variants
• 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
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Title not available (Why is that?)
• Some Notes on K-Harmonic Means Clustering Algorithm
• Degrees of freedom and model selection for \(k\)-means clustering
• Two Modifications of Yinyang K-means Algorithm
• A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems
• Lossy kernelization of same-size clustering
• Lossy kernelization of same-size 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)