Lazy and Eager Approaches for the Set Cover Problem
Ching Lih Lim
Department of Computing and Information Systems
The University of Melbourne,
Victoria 3010, Australia.
Alistair Moffat
Department of Computing and Information Systems
The University of Melbourne,
Victoria 3010, Australia.
Anthony Wirth
Department of Computing and Information Systems
The University of Melbourne,
Victoria 3010, Australia.
Status
Proc. 37th Australasian Computer Science Conference,
Auckland, New Zealand, January 2014, pages 19-27.
Abstract
The SET-COVER problem is tantalizingly simple to describe: given a
collection F of sets, each containing a subset of a universe
U of objects, find a smallest sub-collection A of
F such that every object in U is included in at least
one of the sets in A.
However, like many such combinatorial problems, SET-COVER is NP-hard,
meaning that it is unlikely that an efficient algorithm will be
found, and that approximation algorithms must be preferred for
non-trivial problem instances.
One well-known approximation approach for SET-COVER is to repeatedly
add the set with the most uncovered items to the solution, continuing
until every element in the universe is covered; this GREEDY approach
has a provable logarithmic approximation ratio, essentially the best
feasible ratio.
Here we study the implementation of the GREEDY approach to SET-COVER
evaluating eager and lazy versions and other implementation options.
Experiments with several large datasets demonstrate that lazy ``as
required'' priority queue updates should be preferred, rather than
eager ``as soon as possible'' ones; and that when implemented in this
way, the GREEDY mechanism can solve some large instances of the
SET-COVER problem very quickly.
This practical superiority contrasts with the lazy version's having a
demonstrably higher worst-case operation cost.
Full text
http://crpit.com/confpapers/CRPITV147Lim.pdf.