Bi-criteria linear-time approximations for generalized k-mean/median/center

DOI10.1145/1247069.1247073MaRDI QIDQ3602852zbMATHOpenAlexFDO

Authors Dan Feldman, Danny Segev, Amos Fiat, Micha Sharir

Publication date 12 February 2009

Published in Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• A bi-criteria approximation algorithm for \(k\)-means
• Linear-time approximation schemes for clustering problems in any dimensions
• Automata, Languages and Programming
• On variants of \(k\)-means clustering
• On approximate geometric \(k\)-clustering

Cited in

(7)

• Core-sets: updated survey
• Learning big (image) data via coresets for dictionaries
• Approximation algorithms for orthogonal line centers
• Approximation algorithms for orthogonal line centers
• scientific article; zbMATH DE number 7053357 (Why is no real title available?)
• Greedy minimization of weakly supermodular set functions
• A bi-criteria approximation algorithm for \(k\)-means

This page was built for publication: Bi-criteria linear-time approximations for generalized k-mean/median/center

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