Enumerating Minimal Weight Set Covers
Zahi Ajami, Sara Cohen · 2019
The weighted set cover problem is defined over a universe U of elements, and a set S of subsets of U, each of which is associated with a weight. The goal is then to find a subset C of S that collectively covers U, while having minimal weight. The decision version of this well-known problem is NP-complete, but approximation algorithms have been presented that are guaranteed to find a θS-approximation of the optimal solution, where θSis the harmonic sum of the size of the largest set in S. Finding minimal weight set covers is an important problem, used, e.g., in facility location, team formation and transaction summarization. This paper studies the enumeration version of this problem. Thus, we present an algorithm that enumerates all minimal weight set covers in polynomial delay (i.e., with polynomial time between results) in θS-approximate order. We also present a variant of this algorithm in order to enumerate non-redundant set covers in θS-approximate order. Experimental results show that our algorithms run well in practice over both real and synthetic data.