An improved primal-dual approximation algorithm for the k-means problem with penalties
From MaRDI portal
Publication:5048009
DOI10.1017/S0960129521000104OpenAlexW3193829882MaRDI QIDQ5048009FDOQ5048009
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
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
- Title not available (Why is that?)
- NP-hardness of Euclidean sum-of-squares clustering
- The design of approximation algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Algorithms for facility location problems with outliers. (Extended abstract)
- Clustering large graphs via the singular value decomposition
- A PTAS for k-means clustering based on weak coresets
- A local search approximation algorithm for \(k\)-means clustering
- An improved approximation algorithm for the \(k\)-means problem with penalties
- The seeding algorithm for spherical \(k\)-means clustering with penalties
- The bi-criteria seeding algorithms for two variants of \(k\)-means problem
- Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
Cited In (7)
- 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
- An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
- An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space
- Improved and simplified inapproximability for \(k\)-means
- The seeding algorithm for \(k\)-means problem with penalties
Uses Software
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)
