Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals
Saar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected] · 2026
Read Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals by Saar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16091.txt.
Introduction
Saar Cohen studies grouping when points come in by chance and picks can wait. His 2026 preprint deals with online grouping that has no fixed core point. Points, or agents, reach the system one by one in a chance order. A group pick made too soon can prove poor later. Late picks can use more of the stream as proof.
Cohen asks how long picks can wait and still pay off. He weighs the gain of wait against its cost in time. The maths sets bounds for good wait rules. Such rules serve live systems that group users or tasks. The work adds to the theory of online grouping with chance flow.
Catalog record
| CREATOR | Saar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-16091
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals Saar Cohen Department of Computer Science, Bar Ilan University, Ramat Gan, Israel Department of Computer Science, University of Oxford, Oxford, United Kingdom [email protected] Abstract 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. 1 Introduction In multiplayer online gaming platforms, players enter the platform over time and are assigned to teams for cooperative gameplay (e.g., completing quests or participating in tournaments). Players usually prefer teammates with similar skill levels, playstyles, and compatible roles. Once a player enters the platform, the platform’s team assignment system may postpone the assignment in hope that more compatible players will later join the platform. However, players may become highly unsatisfied if they wait for too long. To optimize their gaming experience, the system should assign players to teams so that players in the same team are more similar to each other than to players in other groups, while minimizing their waiting times for assignments. A widely studied model of clustering is center-based metric clustering [ 30 ] , where elements are points in a metric space whose similarity is measured by distance: closer elements are considered more similar. Clusters are defined by centers, with each point assigned to its nearest center. In contrast, we herein focus on non-centroid metric clustering (see, e.g., [ 11 ] ), with no cluster centers. This captures real-world scenarios where elements (e.g., agents) prefer to be close to others in their cluster, like our gaming platform example, clustered federated learning [ 54 ] , clustering in social networks [ 47 ] , and document clustering [ 42 ] . Other examples include package-delivery services and ride-sharing platforms. For instance, in last-mile delivery, parcels arrive over time and must be dynamically grouped into vehicle loads, where grouping items with nearby destinations reduces travel distance and improves efficiency. Similarly, in ride-sharing platforms, passengers arrive sequentially and the system must form small groups of riders whose pickup and drop-off locations are mutually compatible. Delaying assignment improves batching opportunities but increases waiting time, exactly the tradeoff modeled in our framework. Prior work on non-centroid clustering assumes an offline setting, where all elements are known in advance. However, in many real-world scenarios such as our gaming platform example, the input is revealed gradually over time. For that reason, various online clustering problems have received increased attention in recent years (see, e.g., [ 23 , 45 , 38 , 39 ] ), yet online non-centroid metric clustering has remained largely overlooked. Further, prior works on online clustering often assume that elements are assigned to clusters immediately upon arrival, which may lead to poor solutions in practice. For instance, in our gaming platform example, a perfectly compatible teammate might join the platform just after a player has already been assigned to a team. In this paper, we thus introduce and study a new model of online non-centroid metric clustering with delays , where elements that arrive one at a time as points in a finite metric space must be assigned to clusters, but assignments need not be immediate. Upon arrival, each point’s location is revealed. Then, a central authority (i.e., an online algorithm ) has to irrevocably decide whether to 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 , departing from the more common assumption of immediate decisions upon arrival. This raises a key challenge: our goal is to minimize both the total distance costs between points in each cluster and the total delay costs incurred by postponing decisions. If clusters can be of any size, then the non-centroid clustering of singletons is trivially optimal, as it yields zero total cost. The same applies even if we instead seek a capacitated clustering, where each cluster must respect an upper bound on its size (see, e.g., [ 26 , 53 ] ). Hence, we focus on clustering with fixed-size clusters, where each cluster is required to have a predetermined size (see, e.g., [ 36 ] ). This reflects many real-world scenarios where lack of size constraints can result in highly skewed clusters with arbitrary sizes, where one cluster is significantly larger than the others with small sizes, thus undermining their practical usefulness. For instance, capacity constraints naturally arise from limitations such as the number of customers an individual salesperson can effectively serve. When the number of points is restricted to be even and each cluster must be of size exactly two, our problem reduces to the Min-cost Perfect Matching with Delays (MPMD) problem [ 29 , 6 ] . MPMD is often studied under the classic worst-case (adversarial) model , modeling agents’ arrival order and locations as controlled by an adversary , whose goal is degrading an algorithm’s performance. Here, the performance of an online algorithm is often measured in terms of its competitive ratio [ 31 ] , defined as the worst-case ratio between the algorithm’s total cost and that of an optimal offline solution. However, the worst-case model is overly pessimistic: even if the metric space is known upfront, no online algorithm has a constant competitive ratio [ 5 ] . Contributions. To enable the design of effective algorithms in practice, we consider the unknown i.i.d. (UIID) model, where points’ locations are drawn independently across time from an unknown and fixed probability distribution over the finite metric space. Under the UIID model, we measure the performance of an online algorithm in terms of its ratio-of-expectations (RoE) [ 49 ] , evaluating the expected total costs of an online algorithm with that of an