# A Goemans-Williamson type algorithm for identifying subcohorts in clinical trials

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 33 references that are in the map.
- First posted on arXiv 12 Jun 2025.

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

- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Multiclass Total Variation Clustering](https://mlsanity.com/paper/1306.1185/) (2013)
- [The Price of Explainability for Clustering](https://mlsanity.com/paper/2304.09743/) (2023)
- [Superconstant Inapproximability of Decision Tree Learning](https://mlsanity.com/paper/2407.01402/) (2024)
- [On the Mysteries of MAX NAE-SAT](https://mlsanity.com/paper/2009.10677/) (2020)

## Abstract (arXiv)

We design an efficient algorithm that outputs tests for identifying predominantly homogeneous subcohorts of patients from large in-homogeneous datasets. Our theoretical contribution is a rounding technique, similar to that of Goemans and Wiliamson (1995), that approximates the optimal solution within a factor of 0.82. As an application, we use our algorithm to trade-off sensitivity for specificity to systematically identify clinically interesting homogeneous subcohorts of patients in the RNA microarray dataset for breast cancer from Curtis et al. (2012). One such clinically interesting subcohort suggests a link between LXR over-expression and BRCA2 and MSH6 methylation levels for patients in that subcohort.