On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications

DOI10.1137/070699007zbMATH Open1192.68880OpenAlexW2094048240MaRDI QIDQ3575154FDOQ3575154

Authors: Ke Chen 

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

Recommendations

• On coresets for k-means and k-median clustering
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Towards optimal lower bounds for k-median and k-means coresets
• \(k\)-median clustering under discrete Fréchet and Hausdorff distances
• \(K\)-medoids and other criteria for crisp clustering
• A FAST k-MEANS IMPLEMENTATION USING CORESETS
• Coresets for Fuzzy K-Means with Applications

zbMATH Keywords

high dimensions\(k\)-means clusteringapproximation algorithmsrandom sampling\(k\)-median clusteringcoreset

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cited In (57)

• A faster algorithm for truth discovery via range cover
• A unified framework for clustering constrained data without locality property
• Title not available (Why is that?)
• Coresets for Fuzzy K-Means with Applications
• On the fixed-parameter tractability of capacitated clustering
• Concentration of kernel matrices with application to kernel spectral clustering
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Small space representations for metric min-sum \(k\)-clustering and their applications
• Accurate low-space approximation of metric \(k\)-median for insertion-only streams
• Title not available (Why is that?)
• On parameterized approximation algorithms for balanced clustering
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Approximation and complexity of the capacitated geometric median problem
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Title not available (Why is that?)
• Better streaming algorithms for clustering problems
• Metric \(k\)-median clustering in insertion-only streams
• A strong coreset algorithm to accelerate OPF as a graph-based machine learning in large-scale problems
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Title not available (Why is that?)
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• Probabilistic \(k\)-median clustering in data streams
• Probabilistic \(k\)-median clustering in data streams
• A unified framework of FPT approximation algorithms for clustering problems
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space
• Clustering for metric and nonmetric distance measures
• $k$-median clustering under discrete Fréchet and Hausdorff distances
• On coresets for k-means and k-median clustering
• A PTAS for k-means clustering based on weak coresets
• Tight FPT approximation for socially fair clustering
• Faster balanced clusterings in high dimension
• FPT Approximation for Constrained Metric k-Median/Means
• Clustering problems on sliding windows
• A streaming algorithm for \(k\)-means with approximate coreset
• Small Space Representations for Metric Min-Sum k-Clustering and Their Applications
• Title not available (Why is that?)
• BICO: BIRCH meets coresets for \(k\)-means clustering
• A quantization framework for smoothed analysis of Euclidean optimization problems
• Improved Algorithms for Time Decay Streams
• A bi-criteria analysis for fuzzy \(C\)-means problem
• \(k\)-median clustering under discrete Fréchet and Hausdorff distances
• Approximate range queries for clustering
• Efficient approximation schemes for uniform-cost clustering problems in planar graphs
• A lower bound for metric 1-median selection
• Clustering with faulty centers
• Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• On geometric prototype and applications
• An efficient sum query algorithm for distance-based locally dominating functions
• An efficient sum query algorithm for distance-based locally dominating functions
• Coresets and approximate clustering for Bregman divergences
• Title not available (Why is that?)
• Core-sets: updated survey
• Metric 1-median selection: query complexity vs. approximation ratio
• \(k\)-median/means with outliers revisited: a simple fpt approximation
• FPT approximation for capacitated clustering with outliers

This page was built for publication: On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575154)