Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
Authors: Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi
NeurIPS 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that noisy predictions about the optimal solution can be used to break classical hardness results for maximization problems such as the max-cut problem and more generally, maximization versions of constraint satisfaction problems (CSPs). This proves Lemma 3.6, and hence also Theorem 3.4. The paper does not include experiments. |
| Researcher Affiliation | Collaboration | Vincent Cohen-Addad Google Research France EMAIL Tommaso d Orsi Bocconi University Italy EMAIL Anupam Gupta New York University New York NY 10012 EMAIL Euiwoong Lee University of Michigan Ann Arbor MI 48105 EMAIL Debmalya Panigrahi Duke University Durham NC 27708 EMAIL |
| Pseudocode | No | The algorithms are described in prose (e.g., "The -wide Algorithm" in Section 3.1.1) rather than in a formally structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not include any explicit statements or links indicating that source code for the described methodology is publicly available. The NeurIPS Paper Checklist also notes: "The paper does not include experiments requiring code." and "The paper does not release new assets." |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with datasets, thus it does not provide access information for a training dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets, therefore it does not provide details on training/test/validation splits. |
| Hardware Specification | No | The paper is theoretical and does not include experiments, therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not include experiments, therefore no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not include experiments, therefore no specific experimental setup details like hyperparameters or training configurations are provided. |