Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Parameterized Local Search for Max c-Cut
Authors: Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz
IJCAI 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We finally evaluate our algorithm experimentally when it is applied as postprocessing for a state-of-the-art MAX c-CUT heuristic [Ma and Hao, 2017]. We show that, for a standard benchmark data set, a large fraction of the previously best solutions can be improved by our algorithm, leading to new record solutions for these instances. |
| Researcher Affiliation | Collaboration | 1Friedrich Schiller University Jena, Institute of Computer Science, Germany 2Fraunhofer Institute of Optronics, System Technologies and Image Exploitation, Germany |
| Pseudocode | No | The paper describes algorithms and methods in prose and through mathematical theorems, but it does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not include an explicit statement about releasing source code for the methodology or provide a link to a code repository. |
| Open Datasets | Yes | We used the graphs from the G-set benchmark (https: //web.stanford.edu/ yyye/yyye/Gset/), an established benchmark data set for MAX c-CUT with c {2, 3, 4} (and thus also for MAX CUT) [Benlic and Hao, 2013; Festa et al., 2002; Ma and Hao, 2017; Shylo et al., 2015; Wang et al., 2013; Zhu et al., 2013]. |
| Dataset Splits | No | The paper describes using an 'initial solution' and improving it with a 'hill-climbing algorithm' on a benchmark dataset, but it does not specify any training, validation, or test dataset splits or cross-validation methodology. |
| Hardware Specification | Yes | Each experiment was performed on a single thread of an Intel(R) Xeon(R) Silver 4116 CPU with 2.1 GHz, 24 CPUs and 128 GB RAM. |
| Software Dependencies | Yes | In addition to LS, for each instance we ran standard ILP-formulations1 for MAX c-CUT (again with 30 minute time limit) using the Gurobi solver version 9.5. |
| Experiment Setup | Yes | For each of these graphs, we ran experiments for each c {2, 3, 4} with a time limit of 30 minutes and the published MOH solution as initial solution. |