A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
Authors: Vincent Cohen-Addad, Tommaso D’Orsi, Aida Mousavifar
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the fine-grained complexity of the problem and present the first near-linear time algorithm that achieves similar performances to that of (Makarychev et al., 2012). Our algorithm runs in time O(|V (G)|1+o(1) + |E(G)|1+o(1)) and finds a balanced cut of value O(α) . |
| Researcher Affiliation | Collaboration | 1Google Research 2BIDSA, Bocconi. |
| Pseudocode | Yes | Algorithm 1 Fast and robust algorithm for balanced cut; Algorithm 2 Matrix multiplicative weights algorithm for SDPs; Algorithm 3 Approximate matrix multiplicative weights algorithm for SDPs; Algorithm 4 Fast heavy vertex removal procedure; Algorithm 5 Subroutine of fast heavy vertex removal procedure. |
| Open Source Code | No | The paper does not provide any statements about releasing source code, nor does it include links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve training models on publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic complexity rather than empirical performance on specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and describes algorithms mathematically. It does not mention any specific software packages or libraries with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe an experimental setup with hyperparameters or training configurations for empirical evaluation. |