Conditional covering: greedy heuristics and computational results (Q1091265)

The conditional covering problem is a variation of the set-covering problem which seeks a minimum set of facility sites that will cover not only the given demand points but also one another. Finding an exact solution to the problem is difficult and costly. This paper presents seven greedy heuristics with computational results. Compared with exact integer solutions obtained from LINDO, most of these heuristics seem to perform quite satisfactorily for relatively large problems. The paper also discusses worst-case error bounds for the two best performing heuristics based on the best known bound for set-covering.