On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
From MaRDI portal
Publication:3575154
DOI10.1137/070699007zbMath1192.68880OpenAlexW2094048240MaRDI QIDQ3575154
Publication date: 7 July 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070699007
random samplingapproximation algorithms\(k\)-means clusteringhigh dimensions\(k\)-median clusteringcoreset
Analysis of algorithms and problem complexity (68Q25) Sampling theory, sample surveys (62D05) Approximation algorithms (68W25)
Related Items (40)
A strong coreset algorithm to accelerate OPF as a graph-based machine learning in large-scale problems ⋮ An efficient sum query algorithm for distance-based locally dominating functions ⋮ Unnamed Item ⋮ A lower bound for metric 1-median selection ⋮ Concentration of kernel matrices with application to kernel spectral clustering ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ Clustering with faulty centers ⋮ Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance ⋮ Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ An efficient sum query algorithm for distance-based locally dominating functions ⋮ Tight FPT approximation for socially fair clustering ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ Core-Sets: Updated Survey ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Metric \(k\)-median clustering in insertion-only streams ⋮ Improved Algorithms for Time Decay Streams ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ On Geometric Prototype and Applications ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Faster balanced clusterings in high dimension ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A bi-criteria analysis for fuzzy \(C\)-means problem ⋮ A unified framework for clustering constrained data without locality property ⋮ Metric 1-Median Selection: Query Complexity vs. Approximation Ratio ⋮ Coresets for Fuzzy K-Means with Applications ⋮ A faster algorithm for truth discovery via range cover ⋮ Approximate Range Queries for Clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ On parameterized approximation algorithms for balanced clustering ⋮ Approximation and complexity of the capacitated geometric median problem
This page was built for publication: On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
