CombOpt ReadingGroup - Kevin Cheung-The home-away pattern set feasibility problem in sports scheduling

Abstract:  In sports scheduling, a single round-robin schedule for $2n$ teams consists of $2n-1$ rounds so that each team plays each of the other $2n-1$ teams exactly once across the rounds and that each team plays exactly one game in each round. With each game played at the venue of one of the two opposing teams, a table of home-away patterns can be extracted from a single round-robin schedule so that the $(i,j)$-entry indicates whether team $i$ plays a home game or an away game in round $j$. 

The home-away pattern set feasibility problem turns the process around and asks: Given an arbitrarily constructed table of home-away patterns, is there a single round-robin schedule compatible with it? Even though single round-robin schedules do not often arise in practice, it is not uncommon in sports scheduling to first specify when teams should play home games and then decide on which opponents they should play against. Being able to efficiently determine if a home-away pattern set is feasible can help with quick generation of potential schedules.

As of today, it is not known if the problem is NP-complete. This talk will focus on polynomial-time checkable necessary conditions for feasibility and conditions under which they are also sufficient. Some personal reflections on the problem will conclude the talk.