CS Paper Radar

Competitive Random-Order Correlation k-Clustering

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

cs.DS ·submitted 2026-09-28 16:26 UTC · v2
theory

Abstract

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.

Comment
58 pages, 5 figures, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

Correlation Clustering with Random Partial Information

cs.DS cs.LG ·2026-08-17 ·Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari
theory similarity 0.67
Abstract · 17 pages, 5 figures, 6 tables

Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.

0.26

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering

cs.DS ·2026-09-15 ·Chenglin Fan, Dahoon Lee, Euiwoong Lee
similarity 0.67
Abstract · 37 pages, 2 figures, in submission

We study \emph{pseudometric-weighted correlation clustering}, in which pairs have arbitrary positive or negative labels and nonnegative disagreement weights satisfying the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previous factor of $10/3$. The algorithm constructs an explicit feasible solution to the cluster LP with polynomial support and value at most $(1+\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the minimum integral clustering cost. Our main contribution is a weighted preclustering construction that witnesses a near-optimal clustering while bounding the total weight of admissible edges by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$. We obtain admissibility certificates from random walks, where the factor-two Ptolemy's inequality for pseudometrics reduces the required length of walks from $O(\log n)$ to a constant. We then bound the rounding error separately at each vertex and use the triangle inequality to control its weighted cost. Sampling and coverage corrections produce an exactly feasible solution, and the factor-two rounding completes the approximation algorithm.

0.36

A Simple Active-Set Method for PageRank-Based Local Graph Clustering

cs.DS ·2026-08-17 ·Zhewei Wei, Mingji Yang
similarity 0.64
Abstract · 17 pages

Local graph clustering aims to find a well-connected cluster near a given seed node without exploring the entire graph. A key step in the classic local clustering algorithm of Andersen, Chung, and Lang (ACL; Internet Math. 2007) is to approximate the PageRank vector from the seed node. Their local push method computes an ACL $\varepsilon$-approximate PageRank vector with teleportation parameter $α$ in $O\bigl(1/(α\varepsilon)\bigr)$ time. We give an algorithm that computes an ACL $\varepsilon$-approximate PageRank vector in $\widetilde{O}\bigl(1 / \varepsilon^2\bigr)$ time with high probability. This bound is independent of the graph size and has only a polylogarithmic dependence on $1 / α$, albeit with a quadratic dependence on $1 / \varepsilon$. As a direct consequence, we obtain a new running-time tradeoff between the target conductance and target volume in local graph clustering. Our method also applies to the optimization problem of $\ell_1$-regularized PageRank and computes an additive approximate minimizer with a polylogarithmic dependence on $1/α$, improving the $1/\sqrtα$ dependence in the previous bound of Martínez-Rubio, Wirth, and Pokutta (COLT 2023). Our algorithm is based on an intuitive process that maintains a growing active set of nodes: it performs push operations on the current set until convergence and then expands the set and repeats the process if necessary. We show that for each active set, the corresponding limiting state is the solution to a symmetric diagonally dominant (SDD) linear system on the set. We apply nearly-linear-time SDD solvers to these systems and prove that the approximation preserves the properties of the push process.

0.47

Optimal Online Weighted Connectivity Augmentation

cs.DS ·2026-10-30 ·Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
theory similarity 0.64
Abstract · 32 pages, 12 figures

In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a $k$-edge-connected graph on $n$ vertices and a set of additional edges, called links, with nonnegative costs. Pairs of vertices arrive one by one, and an online algorithm must immediately and irrevocably buy links so that each pair becomes $(k+1)$-edge-connected. The goal is to minimize the total cost of the purchased links. We obtain a deterministic polynomial-time $O(\log n)$-competitive algorithm for WCAP, improving the previous $O(\log^2 n)$ bound (SODA 2026). Our bound is asymptotically optimal, even for randomized algorithms in the random-order model. The general problem reduces to the case where the underlying graph is a cycle, for which link costs in $\{0,1\}$ already yield an $Ω(\log n)$ lower bound. Surprisingly, for unit costs on a cycle, we obtain a deterministic polynomial-time $4$-competitive algorithm, improving the previous $O(\log n)$ bound (SODA 2026), and prove that this ratio is optimal among deterministic algorithms. Thus, with unit costs, cycles are easier than trees, where the optimal competitive ratio is $Θ(\log n)$.

0.25

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time

cs.DS ·2026-11-06 ·Vladimir Braverman, Prathamesh Dharangutte, Chenglin Fan, Chen Wang, Shenghao Xie +1 more
similarity 0.63
Abstract

We present a fully dynamic algorithm for correlation clustering that supports \emph{vertex} insertions and deletions while maintaining an $O(1)$ approximation in polylogarithmic amortized update time. This resolves an open problem of vertex deletions posed by a recent line of work on dynamic correlation clustering. We adopt the min-disagreement objective for correlation clustering, i.e., given a signed complete graph $G=(V,E^+\cup E^-)$, we want to minimize the total number of $(+)$ edge crossing clusters and $(-)$ edges within clusters. The input is given in the adjacency list model, where each update inserts or deletes a node along with its full set of $(+)$ neighbors. Our main technical contribution is a fault-tolerant sparse-dense decomposition framework which unlike the existing decomposition-based frameworks allows for structural inconsistencies as long as the induced cost is bounded. We also show a separation between explicitly maintaining the (stronger) sparse-dense decomposition and maintaining a constant-factor approximation to correlation clustering, which may be of independent interest.

0.28

Optimal Approximation for Constrained Correlation Clustering via Repulsion

cs.DS ·2026-11-03 ·Yixin Cao, Ying Xu
similarity 0.62
Abstract · Superseding arXiv:2608.04883

The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$. We give a randomized polynomial-time $(2+\varepsilon)$-approximation using \emph{Repulsion}, a recursive operation that separates a metric ball from its complement. Repulsion naturally respects hard constraints and admits a short potential-based analysis; as a warm-up, radius-$2/3$ Repulsion rounds the standard metric LP into a feasible partition of cost at most three times its objective. The $(2+\varepsilon)$-approximation takes a two-stage approach, first removing must-links with arbitrarily small loss in the approximation ratio. The second stage combines lossless, constraint-aware preclustering with the bounded sub-cluster LP framework of Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (STOC 2024). Repeated positive conditioning and sampling produce candidate sets, which radius-one Repulsion partitions into feasible clusters at controlled cost. We also give an approximation-preserving reduction from vertex cover to cluster deletion, a special case with only cannot-links. Apart from establishing a matching factor-two hardness threshold under the Unique Games Conjecture, it motivates our two-stage approach and Repulsion.

0.15

Online Vertex Connectivity Augmentation

cs.DS ·2026-11-11 ·Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.62
Abstract · 35 pages

Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of \emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a $k$-vertex-connected graph $F$ and a set of additional purchasable edges (with costs). Demand pairs $(s_1,t_1),(s_2,t_2),\dots$ then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that $s_i$ and $t_i$ become $(k{+}1)$-vertex-connected in the union of $F$ with all edges purchased so far. Our main contribution is an $O((k+\log n)\log n)$-competitive online algorithm for OVCA. We also give an offline $O(k+\log n)$-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of $F$. We note that some dependence on $k$ in the approximation ratio is necessary -- i.e., the problem is hard to approximate within any $\mathrm{polylog}(n)$ factor independent of $k$ -- which shows a separation from the edge-connectivity setting. Finally, specializing to $k=1$, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an $\widetilde O(\log^3 n)$-competitive algorithm for online $\{1,2\}$-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of $1$ or $2$).

0.18

Competitive Online Clustering with Movement Cost

cs.DS ·2026-10-16 ·Christian Coester, Yichen Huang, Michael Mitzenmacher
top venue similarity 0.61
Abstract · To appear in SODA 2027

We study the problem of online clustering with movement cost, which generalizes the fundamental $k$-server problem. At each time step, the algorithm is given a set of points in a metric space and must choose $k$ cluster centers. The cost incurred is the sum of the clustering cost at each time step and the total distance that the centers move over time. Prior work established competitive algorithms for the case $k\in\{1,2\}$ on the line metric with the $k$-median clustering objective; under the $k$-median objective, this problem is also known as facility reallocation. We substantially generalize these results to arbitrary $k$, general metric spaces, and a broad class of clustering objectives. Specifically, we consider clustering costs defined as a norm of the distance vector from points to their nearest center, which subsumes the $k$-median, $k$-center, and (square root of) $k$-means objectives, and provide an asymptotically optimal $O(k)$-competitive randomized algorithm against adaptive online adversaries. The algorithm is based on a reduction to the $k$-server problem, establishing a tight connection between the problems. In this reduction, $k$-server requests are generated by Poisson processes, whose arrival rates evolve in continuous time and are driven by a dual representation of the clustering costs. Our method of using Poissonization in this context may also be of independent interest. We demonstrate another use of the idea by deriving similar reductions for batched set chasing problems. We also consider a different family of clustering objectives defined as a norm of the vector of cluster radii, which subsumes the sum-$k$-radii and the $k$-center objectives, and give a tight $O(k)$-competitive deterministic algorithm on the line.

0.62