Set multi-covering via inclusion-exclusion

Abstract

Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion-exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O* ((2 t)n) time and O* ((t + 1)n) space where t is the maximum value in the coverage requirement set (The O* (f (n)) notation omits a p o l y log (f (n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion-exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)]. © 2009 Elsevier B.V. All rights reserved.