EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Dual-Evaluation Local Search Algorithm for the Minimum Hitting Set Problem

Chenjie Zhou, Xinyun Wu, Mao Luo, Caiquan Xiong, Yuanzhi Ke

Symmetry · 13.11.2026 · 18 (11) · 1902

DOI: 10.3390/sym18111902 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Symmetry, online erschienen am 13.11.2026. Verfasst von Chenjie Zhou und 4 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Minimum Hitting Set (MinHS) problem is a classic NP-hard problem in combinatorial optimization, widely applied across fields such as artificial intelligence diagnosis, bioinformatics, and network monitoring. This paper proposes a local search algorithm with Dual-evaluation mode, named DemHS (Dual-evaluation mode search algorithm), tailored for large-scale hitting set instances. The evaluation employs two types of functions: strong and weak. Strong evaluation accurately calculates the exchange gain by introducing a cross-correction term within the local neighborhood defined by an inserted vertex; meanwhile, weak evaluation quickly estimates the gain through global random sampling to broaden the search scope. These two functions synergistically guide the search process. Furthermore, we introduce an age strategy to break ties and enhance the diversity of the search path. When no improvements are made for extended iterations, a large-scale random perturbation is executed to help the algorithm escape local stagnation. Comparative experiments were conducted using 200 public hitting set instances (100 metaheuristic and 100 exact cases) from PACE-2025. The results show that, in the metaheuristic case group, DemHS improves the record on 62 instances and in the precise case group, DemHS obtains optimal solutions across all tested instances. The ablation studies demonstrate a significant positive gain from the dual-evaluation neighborhood structure on optimization results.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Zhou, C., Wu, X., Luo, M., Xiong, C., & Ke, Y. (2026). A Dual-Evaluation Local Search Algorithm for the Minimum Hitting Set Problem. Symmetry, 18(11), 1902. https://doi.org/10.3390/sym18111902

Vancouver

Zhou C, Wu X, Luo M, Xiong C, Ke Y. A Dual-Evaluation Local Search Algorithm for the Minimum Hitting Set Problem. Symmetry. 2026;18(11):1902. doi:10.3390/sym18111902

BibTeX
@article{Zhou2026,
  author = {Zhou, Chenjie and Wu, Xinyun and Luo, Mao and Xiong, Caiquan and Ke, Yuanzhi},
  title = {A Dual-Evaluation Local Search Algorithm for the Minimum Hitting Set Problem},
  journal = {Symmetry},
  year = {2026},
  volume = {18},
  number = {11},
  pages = {1902},
  doi = {10.3390/sym18111902}
}
Kostenlos starten →