Clustering under approximation stability

DOI10.1145/2450142.2450144MaRDI QIDQ5395707zbMATH OpenOpenAlexFDO

Authors Maria-Florina Balcan, Anupam Gupta, Avrim Blum

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2450142.2450144

zbMATH Keywords

approximation algorithmsclusteringclustering accuracyMin-Sum

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Recommendations

• Approximate clustering without the approximation
• Center-based clustering under perturbation stability
• Clustering with or without the approximation
• Clustering with or without the approximation
• Data stability in clustering: a closer look

Cited in

(21)

• Strategyproof facility location in perturbation stable instances
• Measuring the stability of spectral clustering
• Good (K-means) clusterings are unique (up to small perturbations)
• A unified framework for clustering constrained data without locality property
• \(k\)-means++ under approximation stability
• Clustering with or without the approximation
• Perturbation resilience for the facility location problem
• Clustering with or without the approximation
• scientific article; zbMATH DE number 475546 (Why is no real title available?)
• On the convergence of puck clustering systems
• Approximate clustering without the approximation
• Data stability in clustering: a closer look
• scientific article; zbMATH DE number 2164338 (Why is no real title available?)
• Stable Clusterings and the Cones of Outer Normals
• scientific article; zbMATH DE number 907937 (Why is no real title available?)
• Approximate Clustering with Same-Cluster Queries
• Semi-supervised algorithms for approximately optimal and accurate clustering
• Robust communication-optimal distributed clustering algorithms
• Stability and recovery for independence systems
• Smoothed analysis with adaptive adversaries
• Center-based clustering under perturbation stability

This page was built for publication: Clustering under approximation stability

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