Constant approximation for k-median and k-means with outliers via iterative rounding

DOI10.1145/3188745.3188882zbMath1428.68393arXiv1711.01323OpenAlexW2767218854MaRDI QIDQ5230327

Ravishankar Krishnaswamy, Sai Sandeep, Shi Li

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.01323

zbMATH Keywords

outliersapproximation algorithms\(k\)-means\(k\)-medianiterative rounding

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximation algorithms (68W25)

Related Items (23)

Unnamed Item ⋮ Constant approximation for fault-tolerant median problems via iterative rounding ⋮ Approximation algorithms for clustering with dynamic points ⋮ On some variants of Euclidean \(k\)-supplier ⋮ On clustering with discounts ⋮ Effective Heuristic Techniques for Combined Robust Clustering Problem ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ On colorful vertex and edge cover problems ⋮ How to find a good explanation for clustering? ⋮ Tight FPT approximation for socially fair clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sampling-based dimension reduction for subspace approximation with outliers ⋮ On the cost of essentially fair clusterings ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved approximation for prize-collecting red-blue median ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ Approximation and complexity of the capacitated geometric median problem

This page was built for publication: Constant approximation for k-median and k-means with outliers via iterative rounding