Correlation Clustering with Asymmetric Classification Errors
Authors: Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 [αw, w] and every dissimilar edge e has weight we αw (where α 1 and w > 0 is a scaling parameter). We give a (3 + 2 loge(1/α)) 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/α). |
| Researcher Affiliation | Academia | 1University of Chicago, Chicago, Illinois, USA 2Northwestern University, Evanston, Illinois, USA 3Toyota Technological Institute in Chicago (TTIC), Chicago, Illinois, USA. |
| Pseudocode | Yes | Algorithm 1 Approximation Algorithm |
| Open Source Code | No | The paper does not provide any statements or links regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical analysis and approximation algorithms, and does not conduct experiments on datasets that would require training data. It only mentions datasets in the context of motivating examples from other prior work. |
| Dataset Splits | No | The paper focuses on theoretical analysis and approximation algorithms, and does not conduct experiments that would require validation splits. |
| Hardware Specification | No | The paper does not specify any hardware used for computation or analysis. |
| Software Dependencies | No | The paper does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical analysis and approximation algorithms, and does not describe an experimental setup with hyperparameters or system-level training settings. |