A fast approximation scheme for low-dimensional k-means

zbMATH Open1403.68344arXiv1708.07381MaRDI QIDQ4607907FDOQ4607907

Authors: Vincent Cohen-Addad 

Publication date: 15 March 2018

Full work available at URL: https://arxiv.org/abs/1708.07381

Recommendations

• Local search yields a PTAS for \(k\)-means in doubling metrics
• Linear-time approximation schemes for clustering problems in any dimensions
• A local search approximation algorithm for \(k\)-means clustering
• A local search approximation algorithm for \(k\)-means clustering
• Algorithms and Computation

Mathematics Subject Classification ID

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

Cited In (12)

• Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties
• A refined approximation for Euclidean \(k\)-means
• Title not available (Why is that?)
• Parameterized approximation algorithms and lower bounds for \(k\)-center clustering and variants
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Parameterized \(k\)-clustering: tractability island
• Algorithms and Computation
• Reduced \(k\)-means clustering with MCA in a low-dimensional space
• Improved PTAS for the constrained \(k\)-means problem
• Improved and simplified inapproximability for \(k\)-means
• Fast global \(k\)-means clustering using cluster membership and inequality
• Improving K-means method via shrinkage estimation and LVQ algorithm

This page was built for publication: A fast approximation scheme for low-dimensional \(k\)-means

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