In this paper we exploit concepts from Information Theory to improve the classical Chvatal greedy algorithm for the set covering problem. In particular, we develop a new greedy procedure, called Surprisal-Based Greedy Heuristic (SBH), incorporating the computation of a “surprisal” measure when selecting the solution columns. Computational experiments, performed on instances from the OR-Library, showed that SBH yields a 2.5% improvement in terms of the objective function value over the Chvatal’s algorithm while retaining similar execution times, making it suitable for real-time applications. The new heuristic was also compared with Kordalewski’s greedy algorithm, obtaining similar solutions in much shorter times on large instances, and Grossmann and Wool’s algorithm for unicost instances, where SBH obtained better solutions.

More from our Archive

• DOI: 10.1093/bioinformatics/btad424 2023

  Evaluation of AlphaFold-Multimer prediction on multi-chain protein complexes

  Wensi Zhu, Aditi Shenoy, Petras Kundrotas, Arne Elofsson

• DOI: 10.3390/a16070337 2023

  A Hybrid Model for Analysis of Laser Beam Distortions Using Monte Carlo and Shack–Hartmann Techniques: Numerical Study and Experimental Results

  Ilya Galaktionov, Julia Sheldakova, Alexander Nikitin, Vladimir Toporovsky, Alexis Kudryashov

• DOI: 10.1002/jcc.27187 2023

  Accurate thermochemistry at affordable cost by means of an improved version of the JunChS‐F12 model chemistry

  S. Di Grande, M. Kállay, V. Barone

• DOI: 10.1093/bioinformatics/btad437 2023

  SBOannotator: a Python tool for the automated assignment of systems biology ontology terms

  Nantia Leonidou, Elisabeth Fritze, Alina Renz, Andreas Dräger

• DOI: 10.3390/a16070324 2023

  A Fast Surrogate Model-Based Algorithm Using Multilayer Perceptron Neural Networks for Microwave Circuit Design

  Mohammad (Behdad) Jamshidi, Salah I. Yahya, Saeed Roshani, Muhammad Akmal Chaudhary, Yazeed Yasin Ghadi, Sobhan Roshani

• DOI: 10.1093/bioinformatics/btad418 2023

  KG-Hub—building and exchanging biological knowledge graphs

  J Harry Caufield, Tim Putman, Kevin Schaper, Deepak R Unni, Harshad Hegde, Tiffany J Callahan, Luca Cappelletti, Sierra A T Moxon, Vida Ravanmehr, Seth Carbon, Lauren E Chan, Katherina Cortes, Kent A Shefchek, Glass Elsarboukh, Jim Balhoff, Tommaso Fontana, Nicolas Matentzoglu, Richard M Bruskiewich, Anne E Thessen, Nomi L Harris, Monica C Munoz-Torres, Melissa A Haendel, Peter N Robinson, Marcin P Joachimiak, Christopher J Mungall, Justin T Reese

• DOI: 10.1093/bioinformatics/btad203 2023

  A gated graph transformer for protein complex structure quality assessment and its performance in CASP15

  Xiao Chen, Alex Morehead, Jian Liu, Jianlin Cheng

• DOI: 10.1093/bioinformatics/btad228 2023

  TSignal: a transformer model for signal peptide prediction

  Alexandru Dumitrescu, Emmi Jokinen, Anja Paatero, Juho Kellosalo, Ville O Paavilainen, Harri Lähdesmäki

• DOI: 10.1093/bioinformatics/btad411 2023

  MDTips: a multimodal-data-based drug–target interaction prediction system fusing knowledge, gene expression profile, and structural data

  Xiaoqiong Xia, Chaoyu Zhu, Fan Zhong, Lei Liu

• DOI: 10.3390/a16070343 2023

  Deep Learning for Detecting Verticillium Fungus in Olive Trees: Using YOLO in UAV Imagery

  Marios Mamalis, Evangelos Kalampokis, Ilias Kalfas, Konstantinos Tarabanis