An improved primal-dual approximation algorithm for the k-means problem with penalties

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

zbMATH Keywords

approximation algorithmlinear program\(k\)-means problem with penaltiesJV algorithm

Mathematics Subject Classification ID

Computer science (68-XX)

Uses Software

• k-means++

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