Correlation Clustering and Biclustering with Locally Bounded Errors
Authors: Gregory Puleo, Olgica Milenkovic
ICML 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provide a rounding algorithm which converts fractional clusterings into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions. Solving the problem numerically, we obtained the following values for the parameters: α = 0.465744 γ = 0.0887449 k1 = 0.767566 k2 = 0.117219 k3 = 0.308433. These parameters yield an approximation ratio of roughly 48. |
| Researcher Affiliation | Academia | Gregory J. Puleo PULEO@ILLINOIS.EDU Coordinated Science Lab, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA Olgica Milenkovic MILENKOV@ILLINOIS.EDU Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA |
| Pseudocode | Yes | Algorithm 1 Round fractional clustering x to obtain a discrete clustering, using threshold parameters α, γ with 0 < γ < α < 1/2. Algorithm 2 Round fractional clustering to obtain a discrete clustering, using threshold parameters α, γ with α < 1/2 and γ < α. |
| Open Source Code | No | The paper does not provide any information about open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs, not empirical experiments requiring specific hardware. While it mentions |
| Software Dependencies | No | The paper is theoretical and does not describe an implementation that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithm design and proofs, and does not include details about experimental setups, hyperparameters, or training configurations. |