Approximation algorithms for spherical k-means problem using local search scheme

DOI10.1016/J.TCS.2020.06.029MaRDI QIDQ2220852zbMATH OpenOpenAlexFDO

Authors Dongmei Zhang, M. Li, Yishui Wang, Yu-kun Cheng, Dachuan Xu

Publication date 25 January 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.06.029

zbMATH Keywords

approximation algorithmdata mininglocal searchspherical \(k\)-means

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• The spherical k-means++ algorithm via local search scheme
• The spherical \(k\)-means++ algorithm via local search
• An approximation algorithm for the spherical k-means problem with outliers by local search
• Approximation algorithm for spherical \(k\)-means problem with penalty
• The seeding algorithm for spherical \(k\)-means clustering with penalties

Cites work

• A bi-criteria approximation algorithm for \(k\)-means
• A constant-factor approximation algorithm for the k-median problem
• A local search approximation algorithm for \(k\)-means clustering
• A new approximation algorithm for the k-facility location problem
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Concept decompositions for large sparse text data using clustering
• Effectiveness of local search for geometric optimization
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• Least squares quantization in PCM
• Local Search Heuristics for k-Median and Facility Location Problems
• NP-hardness of Euclidean sum-of-squares clustering
• On approximate geometric \(k\)-clustering
• Spherical k-Means++ Clustering
• The Planar k-Means Problem is NP-Hard
• The seeding algorithms for spherical \(k\)-means clustering
• Tight analysis of a multiple-swap heuristic for budgeted red-blue median

Cited in

(13)

• An improved Bregman k-means++ algorithm via local search
• The spherical \(k\)-means++ algorithm via local search
• Local search algorithm for the spherical \(k\)-means problem with outliers
• The spherical k-means++ algorithm via local search scheme
• An approximation algorithm for the spherical k-means problem with outliers by local search
• Improved local search algorithms for Bregman k-means and its variants
• Approximation algorithm for spherical \(k\)-means problem with penalty
• The seeding algorithms for spherical \(k\)-means clustering
• Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
• Approximation Algorithms for Spherical k-Means Problem with Penalties Using Local Search Techniques
• Local search approximation algorithms for the spherical \(k\)-means problem
• An improved preconditioned unsupervised K-means clustering algorithm

Describes a project that uses

Uses Software

• k-means++

This page was built for publication: Approximation algorithms for spherical \(k\)-means problem using local search scheme

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