# A Surprisal-Based Greedy Heuristic for the Set Covering Problem
## 1 Introduction
[PERSON] et al. [20] presented the TS-IDS algorithm designed for deep web crawling and, then, [PERSON] [21] tested it in a resource management application. [PERSON] and [PERSON] [22] presented a Greedy Randomized Adaptive Procedure (GRASP), in which they first constructed an initial solution through an adaptive randomized greedy function and then applied a local search procedure. [PERSON] and [PERSON] [23] introduced PROGRES, a probabilistic greedy search heuristic which uses diversification schemes along with a learning strategy. Regarding Lagrangian heuristics, we mention the algorithm developed by [PERSON] [24] and later improved by [PERSON] [25], which consists of a sub-gradient optimization procedure coupled with a greedy algorithm and Lagrangian cost fixing. A similar procedure was designed by [PERSON] et al. [26], which includes three phases, _sub-gradient, heuristic_ and _column fixing_, followed by a refining procedure. [PERSON] and [PERSON] [27] proposed a genetic algorithm in which a variable mutation rate and two new operators are defined. Similarly [PERSON] [28] describes an indirect genetic algorithm. In this procedure actual solutions are found by an external decoder function and then another indirect optimization layer is used to improve the result. Lastly, we mention Meta-Raps, introduced by [PERSON] et al. [29], an iterative search procedure that uses randomness as a way to avoid local optima. All the mentioned heuristics present calculation times not compatible with real contexts. For example, [PERSON]'s algorithm [26] produces solutions with an average computing time of about 400 s (on a DECstation 5000/240 CPU), if executed on non-unicost instances from [PERSON]'s OR Library, with \(500\times 5000\) and \(1000\times\) 10,000 as matrix sizes. Indeed, the difficulty of the problem leads to very high computational costs, which has led academics to research heuristics and meta-heuristics capable of obtaining good solutions, as close as possible to the optimal, in a very short time, in order to tackle real-time applications. In this respect, it is worth noting the paper by [PERSON] and [PERSON] [30], in which a comparative study of eight approximation algorithms for the unicost SCP are proposed. Among these there were several greedy variants, fractional relaxations and randomized algorithms. Other investigations carried out over the years include the following: [PERSON] et al. [31], who studied a variant of SCP, called the Large Set Covering Problem (LSCP), in which sets are possibly infinite; [PERSON] et al. [32], who were interested in the difficulty of applying metaheuristics designed for solving continuous optimization problems to the SCP; [PERSON] et al. [33], who proposed another algorithm to solve the SCP by combining an artificial bee colony (ABC) algorithm with local search; [PERSON] et al. [34], who, in order to solve the green ship routing and scheduling problem (GSRSP), developed a set covering model based on route representation which includes berth time-window constraints; finally, an empiric complexity analysis over the set covering problem, and other problems, was recently conducted by [PERSON] et al. [35]. In this paper, we exploit concepts from Information Theory (see [PERSON] [36]) to improve [PERSON]'s greedy algorithm. Our purpose is to devise a heuristic able to improve the quality of the solution while retaining similar execution times to those of [PERSON]'s algorithm, making it suitable for real-time applications. The main contributions of the current work can be summarized as follows. * The development of a real-time algorithm, named Surprisal-Based Greedy Heuristic (SBH), for the fast computation of high quality solutions for the set covering problem. In particular, our algorithm introduces a _surprisal measure_, also known as _self-information_, to partly account for the problem structure while constructing the solution.