Faster algorithms for the constrained \(k\)-means problem

DOI10.1007/s00224-017-9820-7zbMath1387.68296OpenAlexW3021687846MaRDI QIDQ1702850

Anup Bhattacharya, Ragesh Jaiswal, Amit Kumar

Publication date: 1 March 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9820-7

zbMATH Keywords

\(D^2\) samplingconstrained \(k\)-means clustering

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms (68W40) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (12)

Improved PTAS for the constrained \(k\)-means problem ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Tight FPT approximation for socially fair clustering ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Faster balanced clusterings in high dimension ⋮ Lossy kernelization of same-size clustering ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ Lossy kernelization of same-size clustering ⋮ Approximation and complexity of the capacitated geometric median problem

Cites Work

• Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
• On approximate geometric \(k\)-clustering
• Clustering for metric and nonmetric distance measures
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• On k-Median clustering in high dimensions
• A PTAS for k-means clustering based on weak coresets
• A Unified Framework for Clustering Constrained Data without Locality Property

This page was built for publication: Faster algorithms for the constrained \(k\)-means problem