Abstract
In the Correlation Clustering problem, we are given a weighted graph G with its edges labelled as "similar"or "dissimilar"by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar"edges across clusters and "dissimilar"edges within clusters. We study the correlation clustering problem under the following assumption: Every "similar"edge e has weight we ϵ [aw, w] and every "dissimilar"edge e has weight we = aw (where a = 1 and w > 0 is a scaling parameter). We give a (3 + 2 loge (1/a)) approximation algorithm for this problem. This assumption captures well the scenario when classification errors are asymmetric. Additionally, we show an asymptotically matching Linear Programming integrality gap of ϵ(log 1/a).
| Original language | English (US) |
|---|---|
| Title of host publication | 37th International Conference on Machine Learning, ICML 2020 |
| Editors | Hal Daume, Aarti Singh |
| Publisher | International Machine Learning Society (IMLS) |
| Pages | 4591-4600 |
| Number of pages | 10 |
| ISBN (Electronic) | 9781713821120 |
| State | Published - 2020 |
| Event | 37th International Conference on Machine Learning, ICML 2020 - Virtual, Online Duration: Jul 13 2020 → Jul 18 2020 |
Publication series
| Name | 37th International Conference on Machine Learning, ICML 2020 |
|---|---|
| Volume | PartF168147-6 |
Conference
| Conference | 37th International Conference on Machine Learning, ICML 2020 |
|---|---|
| City | Virtual, Online |
| Period | 7/13/20 → 7/18/20 |
Funding
Jafar Jafarov and Yury Makarychev were supported in part by NSF CCF-1718820 and NSF TRIPODS CCF-1934843. Sanchit Kalhan and Konstantin Makarychev were supported in part by NSF TRIPODS CCF-1934931.
ASJC Scopus subject areas
- Computational Theory and Mathematics
- Human-Computer Interaction
- Software