Clustering in the Boolean hypercube in a list decoding regime

DOI10.1007/978-3-642-39206-1_35MaRDI QIDQ5326579zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Elazar Goldenberg

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39206-1_35

zbMATH Keywords

approximation algorithmsclusteringlist decoding

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• Testing of Clustering
• Deterministic \(o(1)\)-approximation algorithms to 1-center clustering with outliers
• Faster algorithms for the constrained k-means problem
• Faster algorithms for the constrained \(k\)-means problem

Cited in

(3)

• Derandomized parallel repetition via structured PCPs
• On approximability of satisfiable k-CSPs. III
• Towards lower bounds on locally testable codes via density arguments

This page was built for publication: Clustering in the Boolean hypercube in a list decoding regime

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