# A Surprisal-Based Greedy Heuristic for the Set Covering Problem
## 3 Experimental Results
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Set** & 1I1 & 1J1 & **Density** & **Range** & **Count** \\ \hline
4 & 200 & 1000 & 2\% & 1–100 & 10 \\
5 & 200 & 2000 & 2\% & 1–100 & 10 \\
6 & 200 & 1000 & 5\% & 1–100 & 5 \\ A & 300 & 3000 & 2\% & 1–100 & 5 \\ B & 300 & 3000 & 5\% & 1–100 & 5 \\ C & 400 & 4000 & 2\% & 1–100 & 5 \\ D & 400 & 4000 & 5\% & 1–100 & 5 \\ E & 50 & 500 & 20\% & 1–100 & 5 \\ NRE & 500 & 5000 & 10\% & 1–100 & 5 \\ NRF & 500 & 5000 & 20\% & 1–100 & 5 \\ NRG & 1000 & 10,000 & 2\% & 1–100 & 5 \\ NRH & 1000 & 10,000 & 5\% & 1–100 & 5 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Instances features: sets 4–6, A-E and NRE-NRH. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Instance** & 1I1 & 1J1 & **Range** & **Density** \\ \hline rail516 & 516 & 47,311 & 1–2 & 1.3\% \\ rail582 & 582 & 55,515 & 1–2 & 1.2\% \\ rail2536 & 2536 & 1,081,841 & 1–2 & 0.4\% \\ rail507 & 507 & 63,009 & 1–2 & 1.3\% \\ rail2586 & 2586 & 920,683 & 1–2 & 0.3\% \\ rail4284 & 4284 & 1,092,610 & 1–2 & 0.2\% \\ rail4872 & 4872 & 968,672 & 1–2 & 0.2\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Instance features: rail sets. of SBH with respect to CH, taking into account all instances, i.e., sets 4-6, _scp_ and _rail_, amounted to 2.5%. We next compared the algorithms on unicost instances, obtained by setting the cost of all columns equal to 1, as in [PERSON] and [PERSON]'s paper [30]. In particular, we compared SBH with the _Altigreedy_ (ALTG) algorithm proposed by [PERSON] and [PERSON] [30], introduced in Section 2.2. The results are shown in Tables 6-8, where the subdivision of instances was the same as before. The additional column \"SBH vs. ALTG\" reports the percentage improvement of SBH with respect to ALTG algorithm. Looking at Tables 6, it is worth noting that the heuristic which performed better was that of [PERSON]. Indeed, our heuristic SBH was worse than KORD by about 3.49%, while it was better than the other two greedy procedures, with a gap of 1.15%. Here, computation times were all comparable and ranged between 0.002 and 0.007 s. SBH improved its performance in larger instances, as shown in Tables 7 and 8. We would like to point out that ALTG and CH produced the same solution cost for all of the instances, except for the _rail_ ones. In particular, SBH yielded an average improvement of 1.50% on CH and ALTG ([30]) on _scp_ instances, and, respectively, 1.39% and 12.97% on _rail_ instances. Comparing SBH and \(KORD\) on the _scp_ instances, we observed that they were very similar with a 0.07% improvement. In the largest instances (Table 8), as said before, it emerged that the computational time of KORD maade it impractical for real-time applications. The analysis showed that, in most cases, SBH produced better solutions than classical [PERSON]'s algorithm. However, in a few instances CH presented a better solution. This phenomenon was attributable to the features of the instances. As shown in the example provided in Section 2.3, SBH immediately recognizes columns that must necessarily be present in the solution, while CH only selects them when they exhibit the lowest unit cost.