Choosing the Right Algorithm With Hints From Complexity Theory
Authors: Shouda Wang, Weijie Zheng, Benjamin Doerr
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments show a remarkably good performance of the Metropolis algorithm, clearly the best of all algorithms regarded for reasonable problem sizes. |
| Researcher Affiliation | Academia | 1 Laboratoire d Informatique (LIX), Ecole Polytechnique, CNRS, Institut Polytechnique de Paris, France 2 Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, China |
| Pseudocode | Yes | Algorithm 1: Template of a k-ary unbiased black-box algorithm for optimizing f. Algorithm 2: Metropolis algorithm for maximizing f Algorithm 3: Sig-c GA for maximizing f |
| Open Source Code | No | The paper does not provide any explicit statements or links for open-source code for the described methodology. |
| Open Datasets | No | The paper defines a synthetic problem called the Deceiving Leading Blocks (DLB) function within the text. It is not an external, publicly available dataset with a concrete access method (link, DOI, etc.). |
| Dataset Splits | No | The paper does not provide specific dataset split information (e.g., percentages, sample counts, or predefined splits) as it works with a synthetic function (DLB) rather than an external dataset that would typically be split into train/validation/test sets. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments. |
| Software Dependencies | No | The paper mentions algorithms like (1+1) EA, UMDA, Metropolis algorithm, and sig-c GA, but does not provide specific software names with version numbers or library dependencies. |
| Experiment Setup | Yes | We used the standard mutation rate p = 1/n for the (1 + 1) EA, population sizes µ = 3n ln n and λ = 12µ for the UMDA (as in [Doerr and Krejca, 2020b]), and temperature parameter α = 3 (greater than 2 + 1 as suggested in Theorem 4) for the Metropolis algorithm. For the sig-c GA, we took ϵ = 2.5... |