1 Search Results for "Devvrit,"

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.33

Robust Correlation Clustering

Authors: Devvrit, Ravishankar Krishnaswamy, and Nived Rajaraman

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract

In this paper, we introduce and study the Robust-Correlation-Clustering problem: given a graph G = (V,E) where every edge is either labeled + or - (denoting similar or dissimilar pairs of vertices), and a parameter m, the goal is to delete a set D of m vertices, and partition the remaining vertices V \ D into clusters to minimize the cost of the clustering, which is the sum of the number of + edges with end-points in different clusters and the number of - edges with end-points in the same cluster. This generalizes the classical Correlation-Clustering problem which is the special case when m = 0. Correlation clustering is useful when we have (only) qualitative information about the similarity or dissimilarity of pairs of points, and Robust-Correlation-Clustering equips this model with the capability to handle noise in datasets. In this work, we present a constant-factor bi-criteria algorithm for Robust-Correlation-Clustering on complete graphs (where our solution is O(1)-approximate w.r.t the cost while however discarding O(1) m points as outliers), and also complement this by showing that no finite approximation is possible if we do not violate the outlier budget. Our algorithm is very simple in that it first does a simple LP-based pre-processing to delete O(m) vertices, and subsequently runs a particular Correlation-Clustering algorithm ACNAlg [Ailon et al., 2005] on the residual instance. We then consider general graphs, and show (O(log n), O(log^2 n)) bi-criteria algorithms while also showing a hardness of alpha_MC on both the cost and the outlier violation, where alpha_MC is the lower bound for the Minimum-Multicut problem.

Cite as

Devvrit, Ravishankar Krishnaswamy, and Nived Rajaraman. Robust Correlation Clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{devvrit_et_al:LIPIcs.APPROX-RANDOM.2019.33,
  author =	{Devvrit and Krishnaswamy, Ravishankar and Rajaraman, Nived},
  title =	{{Robust Correlation Clustering}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.33},
  URN =		{urn:nbn:de:0030-drops-112483},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.33},
  annote =	{Keywords: Correlation Clustering, Outlier Detection, Clustering, Approximation Algorithms}
}

Refine by Author
1 Devvrit
1 Krishnaswamy, Ravishankar
1 Rajaraman, Nived

Refine by Classification
1 Theory of computation → Design and analysis of algorithms
1 Theory of computation → Facility location and clustering

Refine by Keyword
1 Approximation Algorithms
1 Clustering
1 Correlation Clustering
1 Outlier Detection

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Devvrit,"

Robust Correlation Clustering

Abstract

Cite as

Thanks for your feedback!

Could not send message