KKKonstantin Kutzkov
Konstantin Kutzkov
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Konstantin Kutzkov has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
David García-Soriano
Labs Yahoo IT University of Copenhagen Barcelona Copenhagen Spain Denmark
1 shared publicationFrancesco Bonchi
Labs Yahoo IT University of Copenhagen Barcelona Copenhagen Spain Denmark
1 shared publication
Latest Publications
- Open Access
Local correlation clustering
Correlation clustering is perhaps the most natural formulation of clustering. Given $n$ objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its theoretical appeal, the practical relevance of correlation clustering still remains largely unexplored, mainly due to the fact that correlation clustering requires the $\Theta(n^2)$ pairwise similarities as input. In this paper we initiate the investigation into \emph{local} algorithms for correlation clustering. In \emph{local correlation clustering} we are given the identifier of a single object and we want to return the cluster to which it belongs in some globally consistent near-optimal clustering, using a small number of similarity queries. Local algorithms for correlation clustering open the door to \emph{sublinear-time} algorithms, which are particularly useful when the similarity between items is costly to compute, as it is often the case in many practical application domains. They also imply $(i)$ distributed and streaming clustering algorithms, $(ii)$ constant-time estimators and testers for cluster edit distance, and $(iii)$ property-preserving parallel reconstruction algorithms for clusterability. Specifically, we devise a local clustering algorithm attaining a $(3, \varepsilon)$-approximation in time $O(1/\varepsilon^2)$ independently of the dataset size. An explicit approximate clustering for all objects can be produced in time $O(n/\varepsilon)$ (which is provably optimal). We also provide a fully additive $(1,\varepsilon)$-approximation with local query complexity $poly(1/\varepsilon)$ and time complexity $2^{poly(1/\varepsilon)}$. The latter yields the fastest polynomial-time approximation scheme for correlation clustering known to date.Open AccessLocal correlation clustering
Correlation clustering is perhaps the most natural formulation of clustering. Given $n$ objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its theoretical appeal, the practical relevance of correlation clustering still remains largely unexplored, mainly due to the fact that correlation clustering requires the $\Theta(n^2)$ pairwise similarities as input. In this paper we initiate the investigation into \emph{local} algorithms for correlation clustering. In \emph{local correlation clustering} we are given the identifier of a single object and we want to return the cluster to which it belongs in some globally consistent near-optimal clustering, using a small number of similarity queries. Local algorithms for correlation clustering open the door to \emph{sublinear-time} algorithms, which are particularly useful when the similarity between items is costly to compute, as it is often the case in many practical application domains. They also imply $(i)$ distributed and streaming clustering algorithms, $(ii)$ constant-time estimators and testers for cluster edit distance, and $(iii)$ property-preserving parallel reconstruction algorithms for clusterability. Specifically, we devise a local clustering algorithm attaining a $(3, \varepsilon)$-approximation in time $O(1/\varepsilon^2)$ independently of the dataset size. An explicit approximate clustering for all objects can be produced in time $O(n/\varepsilon)$ (which is provably optimal). We also provide a fully additive $(1,\varepsilon)$-approximation with local query complexity $poly(1/\varepsilon)$ and time complexity $2^{poly(1/\varepsilon)}$. The latter yields the fastest polynomial-time approximation scheme for correlation clustering known to date. - 15 July 2012
- Published by Elsevier in Information Processing Letters
- Vol. 112 (13) , 535-539
An exact exponential time algorithm for counting bipartite cliques
- 15 July 2012
- Published by Elsevier in Information Processing Letters
- Vol. 112 (13) , 535-539
An exact exponential time algorithm for counting bipartite cliques