The effectiveness of lloyd-type methods for the k-means problem
From MaRDI portal
Publication:5395696
DOI10.1145/2395116.2395117zbMath1281.68229OpenAlexW2029698681WikidataQ105966079 ScholiaQ105966079MaRDI QIDQ5395696
Leonard J. Schulman, Yuval Rabani, Rafail Ostrovsky, Chaitanya Swamy
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2395116.2395117
Pattern recognition, speech recognition (68T10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (54)
A refined approximation for Euclidean \(k\)-means ⋮ Fast indefinite multi-point (IMP) clustering ⋮ Simultaneous variable weighting and determining the number of clusters -- a weighted Gaussian means algorithm ⋮ Regularity-based spectral clustering and mapping the Fiedler-carpet ⋮ Probably certifiably correct \(k\)-means clustering ⋮ A bad instance for \texttt{k-means++} ⋮ Variational learning of a Dirichlet process of generalized Dirichlet distributions for simultaneous clustering and feature selection ⋮ An investigation on support vector clustering for big data in quantum paradigm ⋮ Oblivious sampling with applications to two-party \(k\)-means clustering ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ On the discrepancy between Kleinberg's clustering axioms and \(k\)-means clustering algorithm behavior ⋮ Global optimality in \(k\)-means clustering ⋮ Biconvex Clustering ⋮ A rank-size approach to analyse soccer competitions and teams: the case of the Italian football league ``Serie A ⋮ Feature-weighted clustering with inner product induced norm based dissimilarity measures: an optimization perspective ⋮ A semi brute-force search approach for (balanced) clustering ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ Convex optimization for the planted \(k\)-disjoint-clique problem ⋮ The planar \(k\)-means problem is NP-hard ⋮ Unnamed Item ⋮ Guaranteed clustering and biclustering via semidefinite programming ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Core-Sets: Updated Survey ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ 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 ⋮ The Parallel Seeding Algorithm for k-Means Problem with Penalties ⋮ Discrepancy minimizing spectral clustering ⋮ The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Good (K-means) clusterings are unique (up to small perturbations) ⋮ Quantile-based clustering ⋮ Unnamed Item ⋮ The Planar k-Means Problem is NP-Hard ⋮ Optimizing cluster structures with inner product induced norm based dissimilarity measures: theoretical development and convergence analysis ⋮ The seeding algorithm for \(k\)-means problem with penalties ⋮ NP-hardness of Euclidean sum-of-squares clustering ⋮ Generalized quasirandom properties of expanding graph sequences ⋮ A unified framework for clustering constrained data without locality property ⋮ Convex programming based spectral clustering ⋮ An efficient k‐means‐type algorithm for clustering datasets with incomplete records ⋮ The seeding algorithms for spherical \(k\)-means clustering ⋮ Parallel Algorithms for Nearest Neighbor Search Problems in High Dimensions ⋮ Center-based clustering under perturbation stability ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ The approximation algorithm based on seeding method for functional \(k\)-means problem ⋮ The bi-criteria seeding algorithms for two variants of \(k\)-means problem ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ Stability and Recovery for Independence Systems ⋮ Unnamed Item ⋮ Approximation algorithm for spherical \(k\)-means problem with penalty ⋮ Unnamed Item ⋮ \(k\)-means++ under approximation stability ⋮ K-means clustering via a nonconvex optimization approach
This page was built for publication: The effectiveness of lloyd-type methods for the k-means problem
