Correlation clustering and biclustering with locally bounded errors

Gregory J. Puleo, Olgica Milenkovic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication33rd International Conference on Machine Learning, ICML 2016
EditorsMaria Florina Balcan, Kilian Q. Weinberger
PublisherInternational Machine Learning Society (IMLS)
Pages1380-1388
Number of pages9
ISBN (Electronic)9781510829008
StatePublished - Jan 1 2016
Event33rd International Conference on Machine Learning, ICML 2016 - New York City, United States
Duration: Jun 19 2016Jun 24 2016

Publication series

Name33rd International Conference on Machine Learning, ICML 2016
Volume2

Other

Other33rd International Conference on Machine Learning, ICML 2016
CountryUnited States
CityNew York City
Period6/19/166/24/16

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Correlation clustering and biclustering with locally bounded errors'. Together they form a unique fingerprint.

  • Cite this

    Puleo, G. J., & Milenkovic, O. (2016). Correlation clustering and biclustering with locally bounded errors. In M. F. Balcan, & K. Q. Weinberger (Eds.), 33rd International Conference on Machine Learning, ICML 2016 (pp. 1380-1388). (33rd International Conference on Machine Learning, ICML 2016; Vol. 2). International Machine Learning Society (IMLS).