Research map / Learning theory and algorithms / Clustering

Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation

AAAI 2024 · Learning theory and algorithms › Clustering · approach: Fair clustering approximation · 3 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that the constant-size swap local-search heuristic for representative (fair-center) k-median gives a (4ℓ+5)-approximation with (ℓ+1)^2-swaps when the number of groups ℓ is constant, and an unbounded ratio when ℓ is superconstant.

Problem

Whether the O(1)-swap local-search heuristic has provable approximation guarantees for representative k-median (fair-center clustering) when the number of demographic groups exceeds 2 was an open question.

Approach

Analyzes local search by constructing test swaps and organizing them into a hierarchy of levels, so that the positive cost terms induced by lower-level swaps are cancelled by multiplying inequalities by level-dependent factors, yielding a linear combination bound on the locally-optimal cost.

Key results

• The (ℓ+1)^2-swap heuristic yields a (4ℓ+5)-approximation for REP-k-MED with ℓ demographic groups.
• Any p-swap heuristic with p < ℓ has a locality gap larger than n^(ℓ-1) - 1, so constant-size swaps fail when ℓ is superconstant.

Measured effects reported in the paper

Surprising findings

• Local search with constant-size swaps has an unbounded approximation ratio when the number of groups grows, despite good empirical performance.

Limitations

• The gap between the swap-size lower bound (ℓ) and the upper bound ((ℓ+1)^2) remains open.
• The approximation constant 4ℓ+5 grows linearly with the number of groups, so guarantees are only constant for fixed ℓ.

Experimental setup

Metrics: approximation ratio locality gap

Baselines: p-swap local search (Thejaswi et al. 2021) block-based analysis for ℓ≤2

Builds on: Arya et al. local search for k-median Friggstad and Zhang red-blue median analysis Hajiaghayi et al. red-blue median local search Thejaswi et al. REP-k-MED

Closest papers by meaning

• Fast Local Search Algorithms for Clustering with Adaptive Sampling and Bandit Strategies (NeurIPS 2025 · similarity 0.90)
• Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms (ICML 2026 · similarity 0.89)
• Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.87)
• Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.87)
• Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.87)
• Competitively Consistent Clustering (ICML 2025 · similarity 0.86)