A fast approximation scheme for low-dimensional k-means

MaRDI QIDQ4607907zbMATHFDO

Authors Vincent Cohen-Addad

Publication date 15 March 2018

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

Mathematics Subject Classification ID

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

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

Cited in

(12)

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

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)