A local search approximation algorithm for \(k\)-means clustering
From MaRDI portal
Publication:598232
DOI10.1016/j.comgeo.2004.03.003zbMath1077.68109OpenAlexW4236385439WikidataQ105988026 ScholiaQ105988026MaRDI QIDQ598232
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (66)
A refined approximation for Euclidean \(k\)-means ⋮ Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems ⋮ Iterative algorithm for discrete structure recovery ⋮ Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem ⋮ Complexity of single-swap heuristics for metric facility location and related problems ⋮ An improved primal-dual approximation algorithm for the k-means problem with penalties ⋮ Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Unnamed Item ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ A three-stage approach for segmenting degraded color images: smoothing, lifting and thresholding (SLaT) ⋮ Approximation Algorithms for Matroid and Knapsack Means Problems ⋮ Effective Heuristic Techniques for Combined Robust Clustering Problem ⋮ Approximation Algorithms for Spherical k-Means Problem with Penalties Using Local Search Techniques ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ The provably good parallel seeding algorithms for the k‐means problem with penalties ⋮ SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ Approximation algorithm for squared metric facility location problem with nonuniform capacities ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Iterative denoising ⋮ Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm ⋮ Global optimality in \(k\)-means clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A novel method for image segmentation using reaction-diffusion model ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ The planar \(k\)-means problem is NP-hard ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Approximation algorithms for spherical \(k\)-means problem using local search scheme ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane ⋮ A Local-Search Algorithm for Steiner Forest ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ The Parallel Seeding Algorithm for k-Means Problem with Penalties ⋮ Improved and simplified inapproximability for \(k\)-means ⋮ \(k\)-means requires exponentially many iterations even in the plane ⋮ Faster balanced clusterings in high dimension ⋮ Frequency-based views to pattern collections ⋮ An approximation ratio for biclustering ⋮ Local search approximation algorithms for the sum of squares facility location problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A local search approximation algorithm for a squared metric \(k\)-facility location problem ⋮ The Planar k-Means Problem is NP-Hard ⋮ A novel 3D mesh compression using mesh segmentation with multiple principal plane analysis ⋮ The spherical \(k\)-means++ algorithm via local search ⋮ Local search algorithm for the spherical \(k\)-means problem with outliers ⋮ The seeding algorithm for \(k\)-means problem with penalties ⋮ Unnamed Item ⋮ A Lottery Model for Center-Type Problems With Outliers ⋮ Agnostic Clustering ⋮ An enhanced genetic algorithm with new mutation for cluster analysis ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ The seeding algorithm for spherical \(k\)-means clustering with penalties ⋮ The spherical \(k\)-means++ algorithm via local search scheme ⋮ An approximation algorithm for the spherical \(k\)-means problem with outliers by local search ⋮ Approximation algorithm for spherical \(k\)-means problem with penalty ⋮ A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem ⋮ Scenario reduction revisited: fundamental limits and guarantees
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Optimal time bounds for approximate clustering
- Self-organization and associative memory
- A near-linear algorithm for the planar 2-center problem
- On approximate geometric \(k\)-clustering
- Accounting for boundary effects in nearest-neighbor searching
- K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
- Geometric clusterings
- Finding Groups in Data
- Centroidal Voronoi Tessellations: Applications and Algorithms
- Least squares quantization in PCM
- Local search heuristic for k-median and facility location problems
- Some Implications of Interactive Graphic Computer Systems for Data Analysis and Statistics
This page was built for publication: A local search approximation algorithm for \(k\)-means clustering
