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
    Commented Aug 24, 2017 at 7:34

1 Answer 1


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 agree to our terms of service and acknowledge you have read our privacy policy.

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