๐Ÿ“–
Knowledge-guided local search for the prize-collecting Steiner tree problem in graphs
Zhang-Hua Fu, Jin-Kao Hao

Knowledge-guided local search for the prize-collecting Steiner tree problem in graphs

Author / Organization:
Science & Mathematics Published 2017 Verification Pending

Overview & Synopsis

The prize-collecting Steiner tree problem in graphs (PCSPG), as well as its rooted variant (RPCST), are target problems of the 11th DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science) Implementation Challenge held in collaboration with ICERM (the Institute for Computational and Experimental Research in Mathematics). To solve these two problems, this paper proposes a knowledge-guided local search algorithm (K-ILS), 1 which integrates dedicated search strategies and explores structure information of problem instances. K-ILS uses an effective swap-vertex operator for tree transformation associated with a discriminating auxiliary evaluation function as well as several knowledge-guided perturbation strategies. K-ILS additionally employs two new path-based move operators to generate neighboring solutions. The computational results achieved on the benchmark instances of the 11th DIMACS Implementation Challenge using the same computing platform and competition rules demonstrate that K-ILS performs very well compared to the leading algorithms of the challenge. We report additional experiments to analyze the impact of the key components to the performance of the proposed algorithm.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Knowledge-guided local search for the prize-collecting Steiner tree problem in graphs
Author / Organization Zhang-Hua Fu, Jin-Kao Hao
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2017
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-210342
Original Source Link Visit Source Page on hal.science »