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

DOI10.1145/1247069.1247073zbMATH Open1221.68270OpenAlexW2145529614MaRDI QIDQ3602852FDOQ3602852

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• Title not available (Why is that?)
• A bi-criteria approximation algorithm for \(k\)-means
• Learning big (image) data via coresets for dictionaries
• Greedy minimization of weakly supermodular set functions
• Core-sets: updated survey
• Approximation algorithms for orthogonal line centers
• Approximation algorithms for orthogonal line centers

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)