An Efficient Algorithm for Finding an Irredundant Set Cover

The set covering problem is considered and an efficient procedure for finding an irredundant cover is presented. For an m × n cover table, the execution time of the procedure is, in the worst case, proportional to mn . Methods are suggested for obtaining alternate irredundant covers based on an initially obtained irredundant cover. The basic cost-independent algorithm is heuristically extended to consider costs so that a reduced-cost irredundant cover can be obtained. A summary of some computational experience is presented, which indicates that the procedure is fast and applicable to large problems.