The Social Golfer Problem


The Social Golfer Problem (SGP) is a combinatorial optimisation problem. The task is to schedule g × p golfers in g groups of p players for w weeks such that no two golfers play in the same group more than once. An instance of the SGP is denoted by the triple g-p-w. The original problem asks for the maximal w such that the instance 8-4-w can be solved.

After the original SGP instance was first posted to the discussion group sci.op-research in 1998, a solution for 9 weeks was soon found. It was also clear that no solution for 11 weeks could exist.
Proof: Suppose w>=11, and observe the schedule of an arbitrary but fixed player α. Each week, α plays in a group with 3 distinct other players. To play for 11 weeks, α would have to partner 3 × 11 > 31 other players.
Whether there exists a solution for 10 weeks was an open question for several years, until Alejandro Aguado constructed an explicit solution for the 8-4-10 instance in 2004 (txt):

Solution methods for the SGP are the subject of my Master's thesis.


Main page