TY - GEN

T1 - Correlation clustering and biclustering with locally bounded errors

AU - Puleo, Gregory J.

AU - Milenkovic, Olgica

N1 - Funding Information:
The authors thank Dimitris Papailiopoulos for helpful discussions. The authors also acknowledge funding from the NSF grants IOS 1339388 and CCF 1527636, 1526875, 1117980. Research of the first author was supported by the IC Postdoctoral Program.

PY - 2016

Y1 - 2016

N2 - We consider a generalized version of the correlation clustering problem, defined as follows. Given a complete graph G whose edges are labeled with + or -, we wish to partition the graph into clusters while trying to avoid errors: -I-edges between clusters or - edges within clusters. Classically, one seeks to minimize the total number of such errors. We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provide a rounding algorithm which converts "fractional clusterings" into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions.

AB - We consider a generalized version of the correlation clustering problem, defined as follows. Given a complete graph G whose edges are labeled with + or -, we wish to partition the graph into clusters while trying to avoid errors: -I-edges between clusters or - edges within clusters. Classically, one seeks to minimize the total number of such errors. We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provide a rounding algorithm which converts "fractional clusterings" into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions.

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

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

M3 - Conference contribution

AN - SCOPUS:84998655162

T3 - 33rd International Conference on Machine Learning, ICML 2016

SP - 1380

EP - 1388

BT - 33rd International Conference on Machine Learning, ICML 2016

A2 - Balcan, Maria Florina

A2 - Weinberger, Kilian Q.

PB - International Machine Learning Society (IMLS)

T2 - 33rd International Conference on Machine Learning, ICML 2016

Y2 - 19 June 2016 through 24 June 2016

ER -