# Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 58 references that are in the map.
- First posted on arXiv 22 Jan 2026.

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

- [Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraints](https://mlsanity.com/paper/1910.01991/) (2019)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Fair-Capacitated Clustering](https://mlsanity.com/paper/2104.12116/) (2021)
- [Facility Location in Evolving Metrics](https://mlsanity.com/paper/1403.6758/) (2014)
- [Consistent k-Median: Simpler, Better and Robust](https://mlsanity.com/paper/2008.06101/) (2020)
- [Proportional Fairness in Non-Centroid Clustering](https://mlsanity.com/paper/2410.23273/) (2024)
- [Social Clustering in Epidemic Spread on Coevolving Networks](https://mlsanity.com/paper/1707.04933/) (2017)
- [Pareto optimal coalitions of fixed size](https://mlsanity.com/paper/1901.06737/) (2019)
- [Online Coalition Formation under Random Arrival or Coalition Dissolution](https://mlsanity.com/paper/2306.16965/) (2023)
- [Online Multi-level Aggregation with Delays and Stochastic Arrivals](https://mlsanity.com/paper/2404.09711/) (2024)
- [Online Matching with Delays and Size-based Costs](https://mlsanity.com/paper/2408.08658/) (2024)
- [Online Matching: Haste makes Waste!](https://mlsanity.com/paper/1603.03024/) (2016)
- [Online matching with delays and stochastic arrival times](https://mlsanity.com/paper/2210.07018/) (2022)
- [Coalition Formation with Bounded Coalition Size](https://mlsanity.com/paper/2306.01378/) (2023)
- [Deterministic Primal-Dual Algorithms for Online k-way Matching with Delays](https://mlsanity.com/paper/2310.18071/) (2023)
- [Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size](https://mlsanity.com/paper/2505.22384/) (2025)

## Built on by (most cited first, 2 of 2)

- [Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions](https://mlsanity.com/paper/2602.14321/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)

## Abstract (arXiv)

Clustering is a fundamental problem, aiming to partition a set of elements, like agents or data points, into clusters such that elements in the same cluster are closer to each other than to those in other clusters. In this paper, we present a new framework for studying online non-centroid clustering with delays, where elements, that arrive one at a time as points in a finite metric space, should be assigned to clusters, but assignments need not be immediate. Specifically, upon arrival, each point's location is revealed, and an online algorithm has to irrevocably assign it to an existing cluster or create a new one containing, at this moment, only this point. However, we allow decisions to be postponed at a delay cost, instead of following the more common assumption of immediate decisions upon arrival. This poses a critical challenge: the goal is to minimize both the total distance costs between points in each cluster and the overall delay costs incurred by postponing assignments. In the classic worst-case arrival model, where points arrive in an arbitrary order, no algorithm has a competitive ratio better than sublogarithmic in the number of points. To overcome this strong impossibility, we focus on a stochastic arrival model, where points' locations are drawn independently across time from an unknown and fixed probability distribution over the finite metric space. We offer hope for beyond worst-case adversaries: we devise an algorithm that is constant competitive in the sense that, as the number of points grows, the ratio between the expected overall costs of the output clustering and an optimal offline clustering is bounded by a constant.