Towards Better-than-2 Approximation for Constrained Correlation Clustering
Authors: Andreas Kalavas, Evangelos Kipouridis, Nithin Varma
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is a proof that, to achieve a better-than-2 approximation for Constrained Correlation Clustering, it suffices to design an efficient solution to the Constrained Cluster LP. Finally, in Section 4 we give a full analysis for our main algorithm and how it achieves its approximation factor of (1.92 + ε). |
| Researcher Affiliation | Academia | 1Max Planck Institute for Informatics & Saarland Informatics Campus, Saarbr ucken, Germany 2Archimedes, Athena Research Center, Athens, Greece 3University of Cologne, Germany. Correspondence to: Andreas Kalavas <EMAIL>. |
| Pseudocode | Yes | Algorithm 1: Local Search; Algorithm 2: Local Search with penalties; Algorithm 3: Simple sampling-based 2-approximation; Algorithm 4: Pivoting Procedure; Algorithm 5: Main Algorithm. |
| Open Source Code | No | The paper discusses algorithms and their theoretical approximation factors but does not contain any statements about code release or links to repositories. |
| Open Datasets | No | The paper is theoretical and focuses on an approximation algorithm for Constrained Correlation Clustering. It defines the problem using abstract graphs and instances, but does not refer to any specific datasets or provide access information for them. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on any specific dataset, therefore, there is no mention of dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and analysis, without conducting any experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and their analysis, without discussing implementation details or specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and their approximation factors without conducting experiments. Consequently, no specific experimental setup details, such as hyperparameters or training configurations, are provided. |