A Recursive Algorithm to Generate Balanced Weekend Tournaments

2018-02-08

Proceedings of the AAAI Conference on Artificial Intelligence, 32

Volume

Thirty-Second AAAI Conference on Artificial Intelligence 2018

Main Track: Planning and Scheduling

In this paper, we construct a Balanced Weekend Tournament, motivated by the real-life problem of scheduling an n-team double round-robin season schedule for a Canadian university soccer league. In this 6-team league, games are only played on Saturdays and Sundays, with the condition that no team has two road games on any weekend. The implemented regular-season schedule for n = 6 was best-possible, but failed to meet an important "compactness" criterion, as the 10-game tournament required more than five weekends to complete. The motivation for this paper was to determine whether an optimal season schedule, satisfying all of the league's constraints on compact balanced play, could be constructed for sports leagues with n > 6 teams. We present a simple recursive algorithm to answer this question for all even n > 6. As a corollary, our construction gives us an explicit solution to a challenging and well-known graph theory question, namely the problem of decomposing the complete directed graph K*2m into 2m–1 directed Hamiltonian cycles of length 2m.

10.1609/aaai.v32i1.12076