Answers are grounded in this paper and cite their sources.
The set k ‐covering problem, an extension of the classical set covering problem, is an important NP‐hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k ‐covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good‐quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLL ccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLL ccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLL ccsm performs better than its competitors in terms of solution quality in most classical instances.
No takes yet. Share an insight, caveat, or question.
Wang et al. (2016) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: