Research map / Learning theory and algorithms / Clustering
Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering
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.
Gives polynomial-time algorithms that compute approximate Pareto sets for bi-objective k-clustering (combinations of k-separation, k-center/diameter, k-median/k-means, k-MSR) with provable approximation factors, and shows experiments on real and synthetic data.
Problem
Clustering with multiple conflicting objectives (e.g., k-separation vs. k-diameter/k-center/k-median/k-means, or two k-center objectives on different metrics) where the Pareto front is needed but exact computation is NP-hard.
Approach
Adapts known approximation algorithms (Hochbaum-Shmoys, Jain-Vazirani primal-dual, Buchem et al. k-MSR, Single Linkage with threshold enumeration, nesting technique) to compute approximate Pareto sets for pairs of clustering objectives, with new faster algorithm for two radius/diameter objectives.
Key results
- For k-separation with k-means, the best approximate Pareto solution improves NMI over k-means++ on all tested data sets (e.g., Iris 0.7405 to 0.8578; 2d-10c-no4 0.9052 to 0.9779).
- Algorithms achieve (1,2)-approx for k-separation with k-diameter/k-center, (2,2)-approx for two k-center objectives in O(n^3) time, and (9,6+eps)/(18,6+eps) for k-center/diameter with k-median.
- Lower-bound examples show that k-separation cannot be simultaneously approximated by constant factors together with k-diameter, k-median, or k-means.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · Rice | NMI: 0.4693 -> 0.4728 | Helped |
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · Dry Bean | NMI: 0.5164 -> 0.5231 | Helped |
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · Wine | NMI: 0.4265 -> 0.4400 | Helped |
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · Optdigits | NMI: 0.7459 -> 0.7627 | Helped |
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · Iris | NMI: 0.7405 -> 0.8578 | Helped |
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · 2d-4c-no3 | NMI: 0.8715 -> 0.9267 | Helped |
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · 2d-10c-no3 | NMI: 0.9065 -> 0.9491 | Helped |
| Choose the best solution from the k-separation and k-means approximate Pareto set instead of k-means++ | k-separation + k-means clustering · 2d-10c-no4 | NMI: 0.9052 -> 0.9779 | Helped |
Surprising findings
- Constant-factor approximations for k-separation and any of the minimization objectives cannot be obtained simultaneously, shown by explicit instances.
- The best Pareto solution often beats the pure k-means++ solution in NMI, and on non-synthetic data sets the best Pareto solutions use a small separation value.
Limitations
- Pareto sets for combinations of k-median and k-means can be exponentially large, and no efficient approximation is known in general for these pairs
- Centers restricted to input points, which is uncommon for k-means
- Experiments are limited to small, low-dimensional data sets with a single hyperparameter setup
Experimental setup
Datasets: Rice Dry Bean Wine Optdigits Iris 2d-4c-no3 2d-10c-no3 2d-10c-no4 German median income data (400 districts) sea level time series from ORA5 and PSMSL tide gauges
Benchmarks: Rice Dry Bean Wine Optdigits Iris 2d-4c-no3 2d-10c-no3 2d-10c-no4
Metrics: NMI Rand Index F-beta score approximation factor k-means cost cluster radius
Baselines: k-means++ Single Linkage Alamdari and Shmoys (4,8)-approximation
Builds on: Hochbaum-Shmoys 2-approximation Jain-Vazirani primal-dual k-median Buchem et al. k-min sum radii Papadimitriou-Yannakakis approximate Pareto sets Lin et al. nesting technique
Closest papers by meaning
- Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach (AAAI 2026 · similarity 0.89)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.89)
- Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation (AAAI 2024 · similarity 0.87)
- The Fairness-Quality Tradeoff in Clustering (NeurIPS 2024 · similarity 0.87)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.87)
- Competitively Consistent Clustering (ICML 2025 · 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.