Heuristics for k-domination models of facility location problems in street networks. (September 2021) - Corcoran, Padraig; Gagarin, Andrei
Highlights: New heuristic methods proposed for finding small-size k-dominating sets in graphs. Empirical evaluation performed with respect to existing methods, using instances of graphs corresponding to street networks. The k-domination problem with respect to this class of graphs models the facility location problem. Experiments with large-scale real world road networks. New methods outperform the existing methods, and the performance gain is more significant for larger values of k . Abstract: We present new greedy and beam search heuristic methods to find small-size k -dominating sets in graphs. The methods are inspired by a new problem formulation which explicitly highlights a certain structure of the problem. An empirical evaluation of the new methods is done with respect to two existing methods, using instances of graphs corresponding to street networks. The k -domination problem with respect to this class of graphs can be used to model real-world facility location problem scenarios. For the classic minimum dominating set ( 1 -domination) problem, all except one methods perform similarly, which is due to their equivalence in this particular case. However, for the k -domination problem with k > 1, the new methods outperform the benchmark methods, and the performance gain is more significant for larger values of k .