Abstract | In the maximum cover problem, we are given a collection of
sets over a ground set of elements and a positive integer w, and we are
asked to compute a collection of at most w sets whose union contains the
maximum number of elements from the ground set. This is a fundamental
combinatorial optimization problem with applications to resource allo-
cation. We study the simplest APX-hard variant of the problem where
all sets are of size at most 3 and we present a 6=5-approximation algo-
rithm, improving the previously best known approximation guarantee.
Our algorithm is based on the idea of ¯rst computing a large packing of
disjoint sets of size 3 and then augmenting it by performing simple local
improvements. |