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 | Conference 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 coheaddad@google.com Tommaso d Orsi Bocconi University Italy tommaso.dorsi@unibocconi.it Anupam Gupta New York University New York NY 10012 anupam.g@nyu.edu Euiwoong Lee University of Michigan Ann Arbor MI 48105 euiwoong@umich.edu Debmalya Panigrahi Duke University Durham NC 27708 debmalya@cs.duke.edu |
| 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. |