On the minimum-cost set-covering problem

The set-covering problem is an optimization problem that models many resource-selection problems. For a smaller scale set-covering problem, a greedy solution is a good approximation compared to the optimal solution. However, as the input size get larger, the ratio bound of the greedy solution May grow and be bounded by a logarithm function. In this papers we explore some other algorithms and generalize the set-covering problem so that each set in the given cover has an, associated cost, which is an arbitrary positive integer instead of one. Since the set-covering problem is known to be NP-complete, it is almost impossible to determine the optimal solution for any large sized problem. Indeed, solving the larger scale set-covering problem would imply an enormous computational effort, in both time and computer memory. In addition, this paper investigates the performance of other algorithms, namely genetic algorithm and simulated annealing algorithms, on the minimal cost set-covering problem.