Local Search for MinimumWeight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
Local Search for MinimumWeight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
复制标题
具有两级配置检查和基于频率的评分功能的最小权重支配集的本地搜索
DOI：
10.1613/jair.5205
复制
发表时间：
2017-01-01
影响因子：
5
通讯作者：
Yin, Minghao
中科院分区：
文献类型：
--
作者：
Wang, Yiyuan;Cai, Shaowei;Yin, Minghao
最小重量主导集（MWDS）问题是对最小主导集（MDS）问题的重要概括。本文为MWDS问题提出了一种新的本地搜索算法，该算法基于两个新想法。第一个想法是一种称为两级配置检查（CC2）的启发主义，它是最近强大的配置检查策略（CC）的新变体，可有效避免最近的搜索路径。第二个想法是基于发现顶点的频率的新评分函数。根据这两个想法的名称，我们的算法称为CC2 FS。实验结果表明，就溶液质量而言，CC2 FS在广泛的MWDS基准方面的表现要比某些最先进的算法要好得多。
The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2 FS, according to the names of the two ideas. The experimental results show that, CC2 FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.