# PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering

arXiv: https://arxiv.org/abs/2601.20157 · HTML: https://mlsanity.com/paper/2601.20157/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 13 of 13)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2111.15571/) (2021)
- [Faster Algorithms for the Constrained k-means Problem](https://mlsanity.com/paper/1504.02564/) (2015)
- [Coreset Clustering on Small Quantum Computers](https://mlsanity.com/paper/2004.14970/) (2020)
- [An algorithm for clustering with confidence-based must-link and cannot-link constraints](https://mlsanity.com/paper/2212.14437/) (2022)
- [Performance analysis of coreset selection for quantum implementation of K-Means clustering algorithm](https://mlsanity.com/paper/2206.07852/) (2022)
- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Clustering by Contour coreset and variational quantum eigensolver](https://mlsanity.com/paper/2312.03516/) (2023)
- [Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling](https://mlsanity.com/paper/2504.20982/) (2025)
- [Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds](https://mlsanity.com/paper/2301.08460/) (2023)
- [A Scalable Global Optimization Algorithm For Constrained Clustering](https://mlsanity.com/paper/2510.22519/) (2025)
- [qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices](https://mlsanity.com/paper/2510.22540/) (2025)

## Abstract (arXiv)

Pairwise-constrained clustering incorporates side information through must-link (ML) and cannot-link (CL) relations between samples. While these constraints can improve cluster quality, they complicate optimization at scale and limit quantum and hybrid approaches through the size of the encoded problem. PASS is a scalable framework for pairwise-constrained k-means that concentrates optimization on a small working subset while updating remaining assignments through re-centering. Cannot-link feasibility under subset-restricted updates is formalized as a list-coloring problem on the induced constraint subgraph, yielding a checkable repair certificate with verifiable outcomes. The same subset restriction produces reduced classical subproblems and smaller quantum formulations, enabling a reduction-based hybrid evaluation under a simulation protocol. Infeasible constraint sets are handled explicitly: the pipeline returns a verifiable repair under stated conditions or reports residual conflicts under the same evaluation protocol. Across diverse benchmarks, PASS attains competitive SSE with lower runtime and returns solutions on instances where strong baselines do not finish within a fixed time budget.