Joeri Sleegers
Universally Hard Hamiltonian Cycle Problem Instances
Sleegers, Joeri; Thomson, Sarah L.; van den Berg, Daan
Authors
Contributors
Thomas Bäck
Editor
Bas van Stein
Editor
Christian Wagner
Editor
Jonathan Garibaldi
Editor
H.K. Lam
Editor
Marie Cottrell
Editor
Faiyaz Doctor
Editor
Joaquim Filipe
Editor
Kevin Warwick
Editor
Janusz Kacprzyk
Editor
Abstract
In 2021, evolutionary algorithms found the hardest-known yes and no instances for the Hamiltonian cycle problem. These instances, which show regularity patterns, require a very high number of recursions for the best exact backtracking algorithm (Vandegriend-Culberson), but don't show up in large randomized instance ensembles. In this paper, we will demonstrate that these evolutionarily found instances of the Hamiltonian cycle problem are hard for all major backtracking algorithms, not just the Vandegriend-Culberson. We compare performance of these six algorithms on an ensemble of 91,000 randomized instances plus the evolutionar-ily found instances. These results present a first glance at universal hardness for this NP-complete problem. Algorithms, source code, and input data are all publicly supplied to the community.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | ECTA 2022 : 14th International Conference on Evolutionary Computation Theory and Applications |
Start Date | Nov 24, 2022 |
End Date | Nov 26, 2022 |
Acceptance Date | Aug 24, 2022 |
Online Publication Date | Nov 24, 2022 |
Publication Date | 2022 |
Deposit Date | Aug 16, 2023 |
Publicly Available Date | Aug 17, 2023 |
Volume | 1 |
Pages | 105-111 |
Book Title | Proceedings of the 14th International Joint Conference on Computational Intelligence |
ISBN | 9789897586118 |
DOI | https://doi.org/10.5220/0011531900003332 |
Related Public URLs | https://ijcci.scitevents.org |
Files
Universally Hard Hamiltonian Cycle Problem Instances
(973 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Comparing communities of optima with funnels in combinatorial fitness landscapes
(2017)
Presentation / Conference Contribution
Multifractality and dimensional determinism in local optima networks
(2018)
Presentation / Conference Contribution
On the Fractal Nature of Local Optima Networks
(2018)
Presentation / Conference Contribution
The effect of landscape funnels in QAPLIB instances
(2017)
Presentation / Conference Contribution
Unexplained Fluctuations in Particle Swarm Optimisation Performance with Increasing Problem Dimensionality
(2023)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search