An improved approximation algorithm for the \(k\)-means problem with penalties

DOI10.1007/978-3-030-18126-0_15OpenAlexW2936766102MaRDI QIDQ2327099

Jianxin Wang, Feng Shi, Zhen Zhang, Qilong Feng

Publication date: 11 October 2019

Full work available at URL: https://doi.org/10.1007/978-3-030-18126-0_15

zbMATH Keywords

approximation algorithm\(k\)-means clusteringprimal-dual

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (12)

An improved primal-dual approximation algorithm for the k-means problem with penalties ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Effective Heuristic Techniques for Combined Robust Clustering Problem ⋮ Approximation Algorithms for Spherical k-Means Problem with Penalties Using Local Search Techniques ⋮ The provably good parallel seeding algorithms for the k‐means problem with penalties ⋮ The Parallel Seeding Algorithm for k-Means Problem with Penalties ⋮ Improved approximation for prize-collecting red-blue median ⋮ The bi-criteria seeding algorithms for two variants of \(k\)-means problem ⋮ Approximation algorithm for spherical \(k\)-means problem with penalty ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem

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