Correlation clustering with noisy partial information

Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan

Correlation clustering with noisy partial information

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value (1 + δ) opt-cost+Oδ (n log3 n) with high probability, where opt-cost is the value of the optimal solution (for every δ > 0). The second algorithm finds the ground truth clustering with an arbitrarily small classification error ν (under some additional assumptions on the instance).

Original language	English (US)
Journal	Journal of Machine Learning Research
Volume	40
Issue number	2015
State	Published - Jan 1 2015

Keywords

Correlation Clustering
Polynomial-Time Approximation Scheme
Semi-Random Model

ASJC Scopus subject areas

Control and Systems Engineering
Software
Statistics and Probability
Artificial Intelligence

Fingerprint Dive into the research topics of 'Correlation clustering with noisy partial information'. Together they form a unique fingerprint.

Cite this

@article{9d4c26af620245318b5cedb762636c5f,

title = "Correlation clustering with noisy partial information",

abstract = "In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value (1 + δ) opt-cost+Oδ (n log3 n) with high probability, where opt-cost is the value of the optimal solution (for every δ > 0). The second algorithm finds the ground truth clustering with an arbitrarily small classification error ν (under some additional assumptions on the instance).",

keywords = "Correlation Clustering, Polynomial-Time Approximation Scheme, Semi-Random Model",

author = "Konstantin Makarychev and Yury Makarychev and Aravindan Vijayaraghavan",

year = "2015",

month = jan,

day = "1",

language = "English (US)",

volume = "40",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

number = "2015",

}

TY - JOUR

T1 - Correlation clustering with noisy partial information

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Vijayaraghavan, Aravindan

PY - 2015/1/1

Y1 - 2015/1/1

N2 - In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value (1 + δ) opt-cost+Oδ (n log3 n) with high probability, where opt-cost is the value of the optimal solution (for every δ > 0). The second algorithm finds the ground truth clustering with an arbitrarily small classification error ν (under some additional assumptions on the instance).

AB - In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value (1 + δ) opt-cost+Oδ (n log3 n) with high probability, where opt-cost is the value of the optimal solution (for every δ > 0). The second algorithm finds the ground truth clustering with an arbitrarily small classification error ν (under some additional assumptions on the instance).

KW - Correlation Clustering

KW - Polynomial-Time Approximation Scheme

KW - Semi-Random Model

UR - http://www.scopus.com/inward/record.url?scp=84984688940&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84984688940&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84984688940

VL - 40

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

IS - 2015

ER -

Correlation clustering with noisy partial information

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Cite this