An improved primal-dual approximation algorithm for the k-means problem with penalties
From MaRDI portal
Publication:5048009
DOI10.1017/S0960129521000104OpenAlexW3193829882MaRDI QIDQ5048009
Chunying Ren, Da-Chuan Xu, Dong-lei Du, Min Li
Publication date: 17 November 2022
Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0960129521000104
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A local search approximation algorithm for \(k\)-means clustering
- Clustering large graphs via the singular value decomposition
- NP-hardness of Euclidean sum-of-squares clustering
- The bi-criteria seeding algorithms for two variants of \(k\)-means problem
- The seeding algorithm for spherical \(k\)-means clustering with penalties
- An improved approximation algorithm for the \(k\)-means problem with penalties
- The Design of Approximation Algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A PTAS for k-means clustering based on weak coresets
- Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering