A local search approximation algorithm for k-means clustering

DOI10.1016/J.COMGEO.2004.03.003zbMATH Open1077.68109OpenAlexW4236385439WikidataQ105988026 ScholiaQ105988026MaRDI QIDQ598232FDOQ598232

Christine D. Piatko, Tapas Kanungo, Ruth Silverman, Nathan S. Netanyahu, David M. Mount, 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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding Groups in Data
• Optimization by Simulated Annealing
• Least squares quantization in PCM
• Self-organization and associative memory
• Accounting for boundary effects in nearest-neighbor searching
• A near-linear algorithm for the planar 2-center problem
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Local search heuristic for k-median and facility location problems
• K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
• Optimal time bounds for approximate clustering
• On approximate geometric \(k\)-clustering
• Geometric clusterings
• Some Implications of Interactive Graphic Computer Systems for Data Analysis and Statistics

Cited In (73)

• Title not available (Why is that?)
• Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm
• Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
• Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• \(k\)-median/means with outliers revisited: a simple fpt approximation
• Effective Heuristic Techniques for Combined Robust Clustering Problem
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
• Approximation algorithms for robust clustering problems using local search techniques
• The Parallel Seeding Algorithm for k-Means Problem with Penalties
• The provably good parallel seeding algorithms for the k‐means problem with penalties
• An enhanced genetic algorithm with new mutation for cluster analysis
• A Streaming Algorithm for k-Means with Approximate Coreset
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• Local search approximation algorithms for the sum of squares facility location problems
• A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM
• 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
• Approximation algorithm for squared metric facility location problem with nonuniform capacities
• A refined approximation for Euclidean \(k\)-means
• The planar \(k\)-means problem is NP-hard
• The seeding algorithm for spherical \(k\)-means clustering with penalties
• Complexity of single-swap heuristics for metric facility location and related problems
• An improved Bregman \(k\)-means++ algorithm via local search
• The spherical \(k\)-means++ algorithm via local search
• Improved local search algorithms for Bregman \(k\)-means and its variants
• The spherical \(k\)-means++ algorithm via local search scheme
• \(k\)-means requires exponentially many iterations even in the plane
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• An approximation ratio for biclustering
• Approximation algorithms for spherical \(k\)-means problem using local search scheme
• A Local-Search Algorithm for Steiner Forest
• A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis
• The Planar k-Means Problem is NP-Hard
• Local search approximation algorithms for the \(k\)-means problem with penalties
• An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee
• Approximate Clustering with Same-Cluster Queries
• Faster balanced clusterings in high dimension
• Algorithms and Computation
• An improved approximation algorithm for squared metric \(k\)-facility location
• SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
• Local search algorithm for the spherical \(k\)-means problem with outliers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• A quantization framework for smoothed analysis of Euclidean optimization problems
• Approximation Algorithms for Aversion k-Clustering via Local k-Median
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space
• Noisy, Greedy and Not so Greedy k-Means++
• Iterative denoising
• Frequency-based views to pattern collections
• Scenario reduction revisited: fundamental limits and guarantees
• Approximation Algorithms for Spherical k-Means Problem with Penalties Using Local Search Techniques
• Title not available (Why is that?)
• A Lottery Model for Center-Type Problems With Outliers
• Approximation Algorithms for Matroid and Knapsack Means Problems
• Improved PTAS for the constrained \(k\)-means problem
• Global optimality in \(k\)-means clustering
• Title not available (Why is that?)
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• An improved primal-dual approximation algorithm for the k-means problem with penalties
• Title not available (Why is that?)
• Agnostic Clustering
• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem
• A novel method for image segmentation using reaction-diffusion model
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• An approximation algorithm for the uniform capacitated \(k\)-means problem
• Improved and simplified inapproximability for \(k\)-means
• The seeding algorithm for \(k\)-means problem with penalties
• An approximation algorithm for the spherical \(k\)-means problem with outliers by local search
• Approximation algorithm for spherical \(k\)-means problem with penalty
• Iterative algorithm for discrete structure recovery

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)