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

DOI10.1016/j.tcs.2020.06.029zbMath1477.68540OpenAlexW3038963769MaRDI QIDQ2220852

Yishui Wang, Dongmei Zhang, Min Li, Da-Chuan Xu, Yu-kun Cheng

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 algorithmlocal searchdata miningspherical \(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)

Related Items (4)

Approximation Algorithms for Spherical k-Means Problem with Penalties Using Local Search Techniques ⋮ 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

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A local search approximation algorithm for \(k\)-means clustering
• NP-hardness of Euclidean sum-of-squares clustering
• On approximate geometric \(k\)-clustering
• A constant-factor approximation algorithm for the \(k\)-median problem
• The seeding algorithms for spherical \(k\)-means clustering
• A new approximation algorithm for the \(k\)-facility location problem
• Approximating $k$-Median via Pseudo-Approximation
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The Planar k-Means Problem is NP-Hard
• A Bi-Criteria Approximation Algorithm for k-Means
• Local Search Heuristics for k-Median and Facility Location Problems
• Least squares quantization in PCM
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Spherical k-Means++ Clustering
• Concept decompositions for large sparse text data using clustering

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