부산대학교 도서관

Summary: ``The set $k$-covering problem (SKCP) is NP-hard and hasimportant real-world applications. In this paper, we propose severalimprovements over typical algorithms for its solution. First, wepresent a multilevel (ML) score heuristic that reflects relevantinformation of the currently selected subsets inside or outside acandidate solution. Next, we propose QCC to overcome the cyclingproblem in local search. Based on the ML heuristic and QCC strategy, wepropose an effective subset selection strategy. Then, we integratethese methods into a local search algorithm, which we called MLQCC. Inaddition, we propose a preprocessing method to reduce the scale of theoriginal problem before applying MLQCC. We further enhance MLQCC forlarge-scale instances using a low-time-complexity initializationalgorithm to determine an initial candidate solution, obtaining the$\rm MLQCC + LI$ algorithm. The performance of the proposed MLQCC and$\rm MLQCC + LI$ is verified through experimental evaluations on bothclassical and large-scale benchmarks. The results show that MLQCC and$\rm MLQCC + LI$ notably outperform several state-of-the-art SKCPalgorithms on the evaluated benchmarks.''