Parameterized Local Search for Max c-Cut
Authors: Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | 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. |