The bi-criteria seeding algorithms for two variants of \(k\)-means problem

DOI10.1007/s10878-020-00537-9zbMath1502.90153OpenAlexW3005654207MaRDI QIDQ2082186

Min Li

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00537-9

zbMATH Keywords

approximation algorithmseeding algorithmspherical \(k\)-means clustering\(k\)-means problem with penalties

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (4)

An improved primal-dual approximation algorithm for the k-means problem with penalties ⋮ 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

Cites Work

• Improved and simplified inapproximability for \(k\)-means
• Clustering large graphs via the singular value decomposition
• NP-hardness of Euclidean sum-of-squares clustering
• The seeding algorithm for \(k\)-means problem with penalties
• The seeding algorithms for spherical \(k\)-means clustering
• An improved approximation algorithm for the \(k\)-means problem with penalties
• Local search approximation algorithms for the \(k\)-means problem with penalties
• Adaptive Sampling for k-Means Clustering
• A Bi-Criteria Approximation Algorithm for k-Means
• Least squares quantization in PCM
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• Spherical k-Means++ Clustering
• The effectiveness of lloyd-type methods for the k-means problem
• Empirical and theoretical comparisons of selected criterion functions for document clustering
• Concept decompositions for large sparse text data using clustering
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The bi-criteria seeding algorithms for two variants of \(k\)-means problem