Dynamic Programming Based Algorithms for Set Multicover and Multiset Multicover Problems

Download Now Date Added: Feb 2010
Format: PDF

Given a universe N containing n elements and a collection of multisets or sets over N, the Multi-Set Multi-Cover (MSMC) problem or the Set Multi-Cover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of Multi-Sets or sets. In this paper, the authors give various exact algorithms for these two problems with or without constraints on the number of times a Multi-Set or set may be chosen.