Suppose you are organising a speed dating event. You are given a graph . The event consists of a number of rounds; in the th round of the event, you must pick a subset such that no appears in two elements of , and for all . (That is, no person may be in two dates at the same time, and the same date may not occur in two rounds.) The event lasts for rounds, finishing when . (That is, when all possible dates have occurred). The ‘idle time’ is defined as .
For example, consider an event for straight men and straight women. Then is the complete bipartite graph , and a simple solution is to have all the men seated around the inside of a ring-shaped table, all the women around the outside, and to have one set rotate around after each round while the other set stays still. In this case, and .
How can you choose the to minimise ?