Grigory Yaroslavtsev:Near Optimal LP Rounding for Correlation Clustering on Complete Graphs

Speaker: Grigory Yaroslavtsev , UPenn

Date: Thursday, April 09, 2015

Time: 3:15 PM to 4:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Grigory Yaroslavtsev: Near Optimal LP Rounding for Correlation Clustering on Complete Graphs

Introduced about 10 years ago by Bansal, Blum and Chawla, correlation clustering has become one of the standard techniques in machine learning and data mining. This due to several advantages of correlation clustering as compared to other standard clustering methods (e.g. k-means):

Correlation clustering only requires qualitative information about similarities between objects. This makes it applicable in scenarios such as crowdsourced duplicate finding when information about similarities between objects is generated by humans.
Correlation clustering doesnÂ’t require the number of clusters to be specified in advance, producing the number of clusters that best fits the data.

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps:

For complete graphs our approximation is 2.06?? for a fixed constant ?, which almost matches the previously known integrality gap of 2.
For complete k-partite graphs our approximation is 3. We also show a matching integrality gap.
For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2.

Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a 2-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a 4-approximation (SICOMP'12).

Joint work with Shuchi Chawla, Konstantin Makarychev and Tselil Schramm.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2014 / Spring 2015.

Created by Rebecca Yadegar Email at Thursday, April 02, 2015 at 6:42 PM.