A streaming algorithm for k-means with approximate coreset

DOI10.1142/S0217595919500064MaRDI QIDQ4631688zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 18 April 2019

Published in Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0217595919500064

zbMATH Keywords

\(k\)-means clusteringapproximation algorithmcoresetstreaming

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• StreamKM++: a clustering algorithm for data streams
• On coresets for k-means and k-median clustering
• StreamKM++, a clustering algorithm for data streams
• Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A local search approximation algorithm for \(k\)-means clustering
• A PTAS for k-means clustering based on weak coresets
• A survey on algorithms for k-means problem and its variants
• Approximating extent measures of points.
• Approximating k-median via pseudo-approximation
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• Improved and simplified inapproximability for \(k\)-means
• Least squares quantization in PCM
• Local search heuristic for k-median and facility location problems
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
• On approximate geometric \(k\)-clustering
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On coresets for k-means and k-median clustering
• Optimal time bounds for approximate clustering
• Polynomial-time approximation schemes for geometric min-sum median clustering
• The hardness of approximation of Euclidean k-means

Cited in

(13)

• Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs
• An approximation algorithm for stochastic multi-level facility location problem with soft capacities
• Approximation algorithms for two variants of correlation clustering problem
• Fair coresets and streaming algorithms for fair \(k\)-means
• BICO: BIRCH meets coresets for \(k\)-means clustering
• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
• A space-optimal data-stream algorithm for coresets in the plane
• StreamKM++: a clustering algorithm for data streams
• StreamKM++, a clustering algorithm for data streams
• Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering
• A generalized k-means problem for clustering and an ADMM-based k-means algorithm
• Coresets for kernel clustering
• Approximation algorithm for min-max correlation clustering problem with penalties

This page was built for publication: A streaming algorithm for \(k\)-means with approximate coreset

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