← All papers
First page of Competitive Random-Order Correlation k-Clustering

Competitive Random-Order Correlation k-Clustering

Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman, Omer Wasim, Tegan Wilson

cs.DS Sep 28, 2026 · v2
All theorems on correlation k-clustering approximation and competitive ratios are formalized in Lean, with proofs generated using Aristotle and Claude and hand-checked statements.
Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is to compute a partition of the vertex set such that the total number of disagreements, i.e. the sum of edges between clusters, and non-edges within clusters, is minimized. In this paper, we study correlation $k$-clustering, in which the total number of clusters is restricted to $k$. Correlation $k$-clustering is NP-hard, and while previous work has presented a polynomial time approximation scheme for constant $k$, there are no known results for general $k$. Our first result is a polynomial-time constant-factor approximation algorithm for correlation $k$-clustering for general $k$. The main focus of this work is in the more challenging online setting. Noting that the best competitive ratio under adversarial arrivals is known to be $Ω(n)$, we concentrate on the well-studied random-order model, where vertices arrive in random order and on arrival of a vertex, edges to its earlier-arrived neighbors are revealed. We prove a surprising lower bound of $Ω(\log k)$-competitiveness for any online algorithm, which can be extended to $Ω(\log n)$ when $k = \text{poly}(n)$. Finally, the main result of this paper is a polylogarithmic upper bound on the competitive ratio for correlation $k$-clustering, using an algorithm inspired by the classic Pivot algorithm for correlation clustering. All theorems have been verified using Lean.

Correlation k-clustering partitions a graph's vertices into at most k clusters while minimizing disagreements. No approximation was known for general k, and the online random-order setting was unexplored.

The authors give a constant-factor offline approximation that reduces to unconstrained correlation clustering and then merges groups. For random-order arrivals, they prove a lower bound using a construction of disjoint cliques plus two singletons. They analyze Pivot-inspired online algorithms: UniformPivot for disjoint cliques and BalancedPivot for general graphs. All theorems were formalized in Lean, with code initially produced by Aristotle, updated with Claude, and statements hand-checked.

The results are a polynomial-time constant-factor approximation, an Ω(log k) lower bound on the competitive ratio (Ω(log n) when k = poly(n)), and a polylogarithmic competitive upper bound for general graphs. The Lean formalization uses only standard axioms and is publicly available on GitHub.