1
$\begingroup$

In my head I like to call this "the matchmaker algorithm", but I suspect it might be an existing thing... then again I don't any answers as of now ... whatever, let me explain:

Imagine that you own a matchmaking agency. At the moment there's Y people who signed up. Your task is to organize meetings where these people will interact with each other, and based on that will find out how well they work together.

The problem is that the meetings take place in a really small room, where at once only X people can be in.

QUESTION: How should you organize the meetings, so that each member of Y had been to a meeting with each other member of Y at least once... while organizing as few meetings as possible? Basically... how to make everyone meet everyone in the quickest way possible?

Obviously Gender/Sexuality are not elements of consideration here... Also, there's no possibility of more people joining the group, all right?

I thought this would be really simple, but it's not... see, let's picture that Y=6 and X=3 So let's have ABCDEF be the people

The simplistic way 1) ABC 2) ABD 3) ABE 4) ABF << with this, both A and B had contact with everyone, so they're out 5) CDE 6) CDF << now CD had contact with everyone, out 7) EF << no need for a third person, this is enough However I kept feeling like this cannot be optimal, as in this example, even if A and B already had contact the first time, they are forced to be in 3 extra meetings. I know repeats are unavoidable, but it felt quite redundant to waste time like this.

The more complex way 1) ABC 2) DEF 3) ACE 4) BDF Hmmm starts to get harder to figure this out... 5) AFC 6) ACD 7) BE This is a much harder algorithm, as it's harder to think of different combinations to have as few repeats as possible... but in this case, both methods gave me the result of 7 meetings.

Now I do predict that different results could come out if X was at least 4, also the results would be quite different depending on how big I'd make the Y, although things would get increasing difficult, especially with the more complex algorithm.

As much as I try, I find this quite complicated, so I wonder... if this an existing thing? Can anyone help?

$\endgroup$
1
$\begingroup$

These are known as covering designs. The minimum number of meetings is the covering number $C(Y,X,2)$. As far as I know there is no general formula for it. Gordon, Kuperberg and Patashnik have some tables with the best constructions known in 1995. In particular, they mention that $C(6,3,2) = 6$.

Rödl showed in an important paper that for $X$ fixed, $C(Y,X,2) = \frac{Y(Y-1)}{X(X-1)} (1 + o(1))$ as $Y \to \infty$, and Gordon, Kuperberg and Patashnik (in a different 1995 paper) give constructions matching this bound (the constructions actually appear in the other cited paper of theirs, but are analyzed in this paper).

$\endgroup$
  • $\begingroup$ Wow, so that's the term for it! Thank you very much. Perhaps I can do something with this then :) $\endgroup$ – Jan Nowak Mar 19 '15 at 7:55
0
$\begingroup$

I'd guess this probably is an existing thing, but I don't know what it is either. I can tell you this can be done with 6 meetings. With Y=6, that means there are 15 possible pairings. Starting with A, fill the room eliminating as many pairings as possible, so:

  • ABC (takes care of AB AC and BC)
  • ADE
  • AFB (we can't do better than 2 here, move on to B)
  • BDE (same here, as B has already been paired with A, C & F and D with E)
  • CDF (this eliminates CD CF & DF)
  • CEF (this eliminates the remaining 2 pairs, CE & EF)

Basically, start with the first person who hasn't meet with everyone else yet. Add a person the haven't met yet. Then add additional people based on how many pairings that eliminates. I'm not sure if this will always be optimal for all values of Y and X however.

$\endgroup$
  • $\begingroup$ What? Huh? <checks> Wow, you're right! 6 tries $\endgroup$ – Jan Nowak Mar 19 '15 at 8:00

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.