Flaws of Termination and Optimality in ADOPT-based Algorithms
Authors: Koji Noshiro, Koji Hasebe
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we present counterexamples to the termination and optimality of ADOPT-based algorithms. The flaws are classified into three types, at least one of which exists in each of ADOPT and seven of its variants that we analyzed. In other words, the algorithms may potentially not terminate or terminate with a suboptimal solution. We also propose an amended version of ADOPT that avoids the flaws in existing algorithms and prove that it has the properties of termination and optimality. |
| Researcher Affiliation | Academia | Koji Noshiro and Koji Hasebe University of Tsukuba noshiro@mas.cs.tsukuba.ac.jp, hasebe@cs.tsukuba.ac.jp |
| Pseudocode | Yes | The pseudocode of our version of ADOPT is presented in Appendix C. |
| Open Source Code | No | The paper states "1Appendices and other supplemental materials are available at https://mas.cs.tsukuba.ac.jp/ noshiro." but does not explicitly state that the source code for the methodology described is provided at this link, making it ambiguous. |
| Open Datasets | No | The paper uses small, synthetic DCOP instances (e.g., Figures 1, 3, 5 with defined cost functions) to demonstrate theoretical counterexamples. These are not presented as publicly available datasets for training, nor are any standard public datasets mentioned for this purpose. |
| Dataset Splits | No | The paper is theoretical and presents counterexamples and proofs; it does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | No specific hardware details (e.g., GPU/CPU models, memory) used for running experiments were mentioned in the paper. |
| Software Dependencies | No | No specific ancillary software details with version numbers (e.g., library or solver names with versions) were provided in the paper. |
| Experiment Setup | No | The paper is theoretical and focuses on proving properties and presenting counterexamples; it does not describe an experimental setup with specific hyperparameters or training configurations. |