A local search approximation algorithm for k-means clustering

DOI10.1016/J.COMGEO.2004.03.003MaRDI QIDQ598232zbMATH OpenOpenAlexWikidataFDO

Authors Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y. Wu

Publication date 6 August 2004

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

Clustering\(k\)-meansComputational geometryApproximation algorithmsLocal search

Mathematics Subject Classification ID

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

Recommendations

• A local search approximation algorithm for \(k\)-means clustering
• On variants of \(k\)-means clustering
• How fast is the \(k\)-means method?
• Algorithms and Computation
• How fast is the \(k\)-means method?

Cites work

• scientific article; zbMATH DE number 41467 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1253040 (Why is no real title available?)
• scientific article; zbMATH DE number 1303535 (Why is no real title available?)
• scientific article; zbMATH DE number 1303609 (Why is no real title available?)
• scientific article; zbMATH DE number 467196 (Why is no real title available?)
• scientific article; zbMATH DE number 3436645 (Why is no real title available?)
• scientific article; zbMATH DE number 1754597 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 1926668 (Why is no real title available?)
• scientific article; zbMATH DE number 6472586 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• A near-linear algorithm for the planar 2-center problem
• Accounting for boundary effects in nearest-neighbor searching
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Finding Groups in Data
• Geometric clusterings
• K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
• Least squares quantization in PCM
• Local search heuristic for k-median and facility location problems
• On approximate geometric \(k\)-clustering
• Optimal time bounds for approximate clustering
• Optimization by simulated annealing
• Self-organization and associative memory
• Some Implications of Interactive Graphic Computer Systems for Data Analysis and Statistics

Cited in

(85)

• The spherical \(k\)-means++ algorithm via local search
• How fast is the \(k\)-means method?
• Noisy, Greedy and Not so Greedy k-Means++
• The effectiveness of Lloyd-type methods for the \(k\)-means problem
• Approximation Algorithms for Spherical k-Means Problem with Penalties Using Local Search Techniques
• The seeding algorithm for \(k\)-means problem with penalties
• \(k\)-means requires exponentially many iterations even in the plane
• A streaming algorithm for \(k\)-means with approximate coreset
• The Planar k-Means Problem is NP-Hard
• Iterative denoising
• Faster balanced clusterings in high dimension
• Approximation algorithms for stochastic clustering
• scientific article; zbMATH DE number 1926668 (Why is no real title available?)
• Local search algorithm for the spherical \(k\)-means problem with outliers
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• A local search approximation algorithm for \(k\)-means clustering
• An improved approximation algorithm for squared metric \(k\)-facility location
• How fast is the \(k\)-means method?
• A novel method for image segmentation using reaction-diffusion model
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Complexity of single-swap heuristics for metric facility location and related problems
• Approximation Algorithms for Matroid and Knapsack Means Problems
• An approximation algorithm for the spherical \(k\)-means problem with outliers by local search
• Approximation algorithm for spherical \(k\)-means problem with penalty
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• An efficient enhanced \(k\)-means clustering algorithm
• Local search approximation algorithms for the \(k\)-means problem with penalties
• Iterative algorithm for discrete structure recovery
• A FAST k-MEANS IMPLEMENTATION USING CORESETS
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Frequency-based views to pattern collections
• Improved local search algorithms for Bregman \(k\)-means and its variants
• The spherical \(k\)-means++ algorithm via local search scheme
• SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
• An approximation algorithm for the uniform capacitated \(k\)-means problem
• An approximation ratio for biclustering
• Global optimality in \(k\)-means clustering
• A three-stage approach for segmenting degraded color images: smoothing, lifting and thresholding (SLaT)
• Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
• An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee
• The planar \(k\)-means problem is NP-hard
• Algorithms and Computation
• An improved primal-dual approximation algorithm for the \(k\)-means problem with penalties
• The seeding algorithm for spherical \(k\)-means clustering with penalties
• A quantization framework for smoothed analysis of Euclidean optimization problems
• Approximation algorithms for spherical \(k\)-means problem using local search scheme
• A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis
• A Lottery Model for Center-Type Problems With Outliers
• A local-search algorithm for Steiner forest
• An improved Bregman \(k\)-means++ algorithm via local search
• A refined approximation for Euclidean \(k\)-means
• On variants of \(k\)-means clustering
• Improved and simplified inapproximability for \(k\)-means
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• Scenario reduction revisited: fundamental limits and guarantees
• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem
• Local search approximation algorithms for the sum of squares facility location problems
• scientific article; zbMATH DE number 7561533 (Why is no real title available?)
• A fast approximation scheme for low-dimensional \(k\)-means
• Approximation Algorithms for Aversion k-Clustering via Local k-Median
• Approximate Clustering with Same-Cluster Queries
• A bi-criteria approximation algorithm for \(k\)-means
• An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• Almost optimal solutions to \(k\)-clustering problems
• scientific article; zbMATH DE number 7650078 (Why is no real title available?)
• \(k\)-median/means with outliers revisited: a simple fpt approximation
• Temporal clustering
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
• Improved PTAS for the constrained \(k\)-means problem
• scientific article; zbMATH DE number 7651196 (Why is no real title available?)
• The Parallel Seeding Algorithm for k-Means Problem with Penalties
• An enhanced genetic algorithm with new mutation for cluster analysis
• The provably good parallel seeding algorithms for the k‐means problem with penalties
• A survey on theory and algorithms for \(k\)-means problems
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• Effective Heuristic Techniques for Combined Robust Clustering Problem
• Agnostic clustering
• Approximation algorithms for robust clustering problems using local search techniques
• Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm
• Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
• Smoothed analysis of the squared Euclidean maximum-cut problem

Describes a project that uses

Uses Software

• clusfind

This page was built for publication: A local search approximation algorithm for \(k\)-means clustering

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