Optimization of the polynomial greedy solution for the set covering problem

Abstract

This paper proposes a modification of the known and widely used approximate greedy solution for the Set Cover Problem - GREEDYSETCOVER algorithm. Additionally the already known optimizations are presented and ability of their cohesion with the newly presented algorithm is confirmed. The proposed modification of the algorithm,OPTIMIZEDSETCOVER, in the best case, gives optimal results opposite to the GREEDYSETCOVER algorithm. In the worst case, it gives the same results as the GREEDYSETCOVER solution without going out of the polynomial time boundary.