Abstract | We consider the frugal coverage problem, an interesting vari-
ation of set cover deŻned as follows. Instances of the problem consist of
a universe of elements and a collection of sets over these elements; the
objective is to compute a subcollection of sets so that the number of
elements it covers plus the number of sets not chosen is maximized. The
problem was introduced and studied by Huang and Svitkina [7] due to
its connections to the donation center location problem. We prove that
the greedy algorithm has approximation ratio at least 0:782, improving
a previous bound of 0:731 in [7]. We also present a further improvement
that is obtained by adding a simple corrective phase at the end of the
execution of the greedy algorithm. The approximation ratio achieved in
this way is at least 0:806. Our analysis is based on the use of linear
programs which capture the behavior of the algorithms in worst-case
examples. The obtained bounds are proved to be tight. |