Local Correlation Clustering with Asymmetric Classification Errors
Authors: Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we study the task of minimizing local objectives (Definition 1.1) under the Correlation Clustering with Asymmetric Classification Errors model (Definition 1.2). Our main result is an O (1/α) 1/2 1/2p log 1/α approximation algorithm for minimizing the ℓp norm of the disagreements vector, which we now state. Theorem 1.3. There exists a polynomial-time O (1/α) 1/2 1/2p log 1/α -approximation algorithm for the ℓp objective in the Correlation Clustering with Asymmetric Classification Errors model. ...We compliment our positive result (Theorem 1.3) by showing that it is likely to be the best possible based on the natural convex program, by providing an almost matching integrality gap. |
| Researcher Affiliation | Academia | 1University of Chicago, Chicago, IL, USA 2Northwestern University, Evanston, IL, USA 3TTIC, Chicago, IL, USA. |
| Pseudocode | Yes | Algorithm 1 Correlation Clustering Algorithm ... Algorithm 2 Metric Space Partitioning Scheme ... Algorithm 3 Cluster Select |
| Open Source Code | No | The paper does not provide any statements about open-source code availability or links to repositories. |
| Open Datasets | No | The paper is theoretical and does not involve empirical evaluation on datasets. Therefore, no information regarding publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets. Therefore, no information regarding dataset splits for training, validation, or testing is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe running experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe running experiments. While it discusses convex programming, it does not mention specific software or library dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe running experiments. Therefore, no experimental setup details like hyperparameters or training configurations are provided. |