Research map / Learning theory and algorithms / Clustering
Fast Local Search Algorithms for Clustering with Adaptive Sampling and Bandit Strategies
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes faster local search clustering algorithms that use adaptive sampling and bandit strategies to avoid scanning the full dataset for each center swap.
Problem
Local search clustering with distance-based sampling gives constant approximations in linear time, but each iterative center swap requires scanning the entire dataset, limiting scalability.
Approach
Combines adaptive sampling with bandit-style strategies to select candidate centers and evaluate swaps using subsets of data rather than full scans, aiming to keep approximation guarantees while reducing running time.
Closest papers by meaning
- A Sampling-Based Approach for Efficient Clustering in Large Datasets (CVPR 2022 · similarity 0.90)
- Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation (AAAI 2024 · similarity 0.90)
- Linear Time Algorithms for k-means with Multi-Swap Local Search (NeurIPS 2023 · similarity 0.90)
- Greedy Sampling for Approximate Clustering in the Presence of Outliers (NeurIPS 2019 · similarity 0.89)
- Cakewalk Sampling (AAAI 2020 · similarity 0.89)
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.