Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  tvladeck May 30 '12 at 22:00
1  
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 –  Gerhard Paseman May 30 '12 at 22:44
    
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. –  tvladeck May 30 '12 at 23:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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