Journal
KNOWLEDGE-BASED SYSTEMS
Volume 203, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.knosys.2020.106136
Keywords
Heuristic; Computational methods; Cyclic bandwidth minimization; Graph labeling; Combinatorial optimization
Categories
Funding
- Franco-Chinese PHC Cooperation Program [41342NC]
- China Scholarship Council [201608070103]
- Mexican Secretariat of Public Education [00114]
Ask authors/readers for more resources
The Cyclic Bandwidth Problem is an important graph labeling problem with numerous applications. This work aims to advance the state-of-the-art of practically solving this computationally challenging problem. We present an effective heuristic algorithm based on the general iterated local search framework and integrating dedicated search components. Specifically, the algorithm relies on a simple, yet powerful local optimization procedure reinforced by two complementary perturbation strategies. The local optimization procedure discovers high-quality solutions in a particular search zone while the perturbation strategies help the search to escape local optimum traps and explore unvisited areas. We present intensive computational results on 113 benchmark instances from 8 different families, and show performances that are never achieved by current best algorithms in the literature. (C) 2020 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available