Correlation clustering with local objectives
Authors: Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study algorithms for minimizing q norms (q 1) of the disagreements vector for both arbitrary and complete graphs. We present the first known algorithm for minimizing the q norm of the disagreements vector on arbitrary graphs and also provide an improved algorithm for minimizing the q norm (q 1) of the disagreements vector on complete graphs. We also study an alternate cluster-wise local objective introduced by Ahmadi, Khuller and Saha (IPCO 19), which aims to minimize the maximum number of disagreements associated with a cluster. We also present an improved (2 + ")-approximation algorithm for this objective. Finally, we compliment our algorithmic results for minimizing the q norm of the disagreements vector with some hardness results. |
| Researcher Affiliation | Academia | Sanchit Kalhan Konstantin Makarychev Timothy Zhou - No explicit affiliations are provided in the given text. |
| Pseudocode | Yes | A complete description of the algorithm can be found in Figure B.1 (supplementary material). |
| Open Source Code | No | The paper mentions supplemental materials for the full version, but there is no explicit statement about making the source code available or providing a link to a repository for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on algorithm design and approximation ratios, and thus does not describe experiments performed on datasets. |
| Dataset Splits | No | This is a theoretical paper that focuses on algorithm design and analysis, and therefore does not include information about dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper that presents algorithmic results and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper discusses theoretical algorithms and their properties, and thus does not specify software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This paper focuses on theoretical algorithmic contributions and does not provide details on experimental setup, hyperparameters, or system-level training settings. |