The set cover problem (SCP)  is a classical question in combinatorics, computer science and complexity theory.

Briefly, a set of elements and a set of sets that contains different elements are given. Each set has an associated cost. The goal is cover every elements paying the less cost possible.

The partial set cover is a slightly different problem, in which is required to cover at least a given percentage of items paying the less cost possible. The problem is known to be NP-complete, but using approximation good results can be achieved with ease. In the following we analyze the correctness of a greedy approximation algorithm for partial set cover.

This work was done in collaboration with Romolo Marotta during preparation for the exam of Theoretical Computer Science at University “La Sapienza” – Italy