Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction

DOI10.4230/LIPIcs.ESA.2019.40OpenAlexW2978778643MaRDI QIDQ5075781

Haikuo Yu, Zixiu Wang, Hu Ding

Publication date: 11 May 2022

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

zbMATH Keywords

outliersrandom samplingdoubling metricscoreset\(k\)-center clustering

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (4)

Fully dynamic \(k\)-center clustering with outliers ⋮ Fully dynamic \(k\)-center clustering with outliers ⋮ Unnamed Item ⋮ Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers

Uses Software

• CIFAR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relative \((p,\varepsilon )\)-approximations in geometry
• Clustering to minimize the maximum intercluster distance
• Time bounds for selection
• Foundations of data science
• Learnability and the Vapnik-Chervonenkis dimension
• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
• Approximate clustering via core-sets
• Bypassing the embedding
• Better streaming algorithms for clustering problems
• Adaptive Sampling for k-Means Clustering
• A Best Possible Heuristic for the k-Center Problem
• Testing of Clustering
• A local search approximation algorithm for k-means clustering
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Improved bounds on the sample complexity of learning

This page was built for publication: Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction