1
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\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, 2012 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$ May 30, 2012 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, 2012 at 23:32

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.