Turbo-charging is a recent algorithmic technique that is based on the fixed-parameter tractability of the dynamic versions of some problems as a way to improve heuristics. We demonstrate the effectiveness of this technique and develop the turbo-charging idea further. A new hybrid heuristic for the Dominating Set problem that further improves this method is obtained by combining the turbo-charging technique with other standard heuristic tools including Local Search (LS). We implement both the recently proposed “turbo greedy” algorithm of Downey et al.  and a new method presented in this paper. The performance of these new heuristics is assessed on three suites of benchmark datasets, namely DIMACS, BHOSLIB and KONECT. Experiments comparing our algorithm to both heuristic and exact algorithms demonstrate its effectiveness. Our algorithm often produced results that were either exact or better than all the other available algorithms.
|Number of pages||12|
|Journal||Lecture Notes in Computer Science|
|Publication status||Published - 1 Jan 2017|
|Event||Conference on Theory and Applications of Models of Computation - Bern, Switzerland|
Duration: 20 Apr 2017 → 22 Apr 2017
Conference number: 14th
http://www.tamc2017.unibe.ch/ (Link to Conference Website)