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

DOI10.1017/S0960129521000104MaRDI QIDQ5048009zbMATH OpenOpenAlexFDO

Authors Chunying Ren, Dachuan Xu, Donglei Du, M. 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)

Recommendations

• An improved approximation algorithm for the \(k\)-means problem with penalties
• A local search approximation algorithm for the \(k\)-means problem with penalties
• Local search approximation algorithms for the \(k\)-means problem with penalties
• The seeding algorithm for \(k\)-means problem with penalties
• Approximation algorithm for spherical \(k\)-means problem with penalty

Cites work

• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• A PTAS for k-means clustering based on weak coresets
• A local search approximation algorithm for \(k\)-means clustering
• Algorithms for facility location problems with outliers. (Extended abstract)
• An improved approximation algorithm for the \(k\)-means problem with penalties
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Clustering large graphs via the singular value decomposition
• NP-hardness of Euclidean sum-of-squares clustering
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• The bi-criteria seeding algorithms for two variants of \(k\)-means problem
• The design of approximation algorithms
• The seeding algorithm for spherical \(k\)-means clustering with penalties

Cited in

(8)

• The seeding algorithm for \(k\)-means problem with penalties
• A local search approximation algorithm for the \(k\)-means problem with penalties
• Local search approximation algorithms for the \(k\)-means problem with penalties
• An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
• An improved approximation algorithm for the \(k\)-means problem with penalties
• Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
• Improved and simplified inapproximability for \(k\)-means
• An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: An improved primal-dual approximation algorithm for the \(k\)-means problem with penalties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048009)