I'm working on an application for which I want to take the set $C$ of all the possible $k$-combinations of elements in $M$ (with $||M|| = m$), and cover $C$ with the sets of $k$-combinations of subsets $N_i$ of $M$, with $||N_i|| = n < m$ $\forall$ $N_i$

So there are $m \choose k$ combinations to cover, and each set $Q_i$ of $n$ elements will contain $n \choose k$ combinations.

What I'd like is an algorithm that constructs the sets $Q_i$ such that $q$ is minimized (i.e., as close to $m \choose k$ $/$ $n \choose k$ as possible)

So, for example, if $m = 100$, $k = 3$, and $n = 10$, I would want the smallest set of sets of $10$ elements such that their respective sets of $3$-combinations covered the set of $100 \choose 3$ $3$-combinations of M.


The magic words are "design" (if the minimum can be realized) and "covering design" otherwise. There is a vast literature and no algorithm.

  • $\begingroup$ it's amazing how important it is to know which words to search for. thanks chris! i am obviously not a professional mathematician, so i didn't know where to look. $\endgroup$ – tvladeck May 30 '12 at 22:00
  • 2
    $\begingroup$ La Jolla covering repository. And there are algorithms, they are just not guaranteed optimal in all cases. If pretty good is acceptable, there are a few such. A paper by Kuperberg (and Patashnik and others?) provides a good reference point and some algorithms. Gerhard "Ask Me About System Design" Paseman, 2012.05.30 $\endgroup$ – Gerhard Paseman May 30 '12 at 22:44
  • $\begingroup$ Thanks Gerhard! Pretty good, in this case, is definitely acceptable, and in retrospect I should have made that clear. I will check the La Jolla repository. $\endgroup$ – tvladeck May 30 '12 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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