Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ number of times using minimum number of sets from $\mathcal{C}$. (When $k=1$, the problem reduces to min-set cover).

Are there any heuristics out there with 'good' performance on 'real' data for $n=1000$ and $|\mathcal{C}| = 1000$?

  • $\begingroup$ Have you tried formulating this as an ILP and running off the shelf solvers? $\endgroup$ – daniello Aug 24 '17 at 7:34

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M.

See also

  • The documentation of algorithm D, which describes the basic file format; the documentation of algorithm M just explains the changes made to generalise it;
  • the latest preprint of fascicle 5c of The Art of Computer Programming, which at some point will get as far as explaining the algorithm, but already has a number of exercises that will give you an idea of the problems that Knuth has solved with it.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.