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 $\Omega(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 $\Omega(\log k)$-competitiveness for any online algorithm, which can be extended to $\Omega(\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.
Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother clustering criteria in the past three decades. In this paper we give an efficient approximation scheme for this problem that r...
S. KarthikC, Euiwoong Lee, Y. Rabani et al.· 0 citations
The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two st...
A low-degree polynomial lower bound is established showing that clustering is hard as long as the separation $\Delta$ satisfies $\Delta^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$, up to polylogarithmic factors.
Alexandra Carpentier, Nicolas Verzelen· 0 citations
The $k$-center problem is one of the most fundamental clustering problems and has applications in a wide range of areas, including facility location, network design, data mining, and machine learning. Given a set of objects together with a distance measure, the goal is to select $k$ centers such that the maximum distan...
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 complemen...
We design adversarially robust algorithms for dynamic geometric streams that $(1 + \epsilon)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(\epsilon^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk...
Cheng-Zhi Guo, S. Jiang, Robert Krauthgamer et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.