Author:

Keywords:

Sport scheduling, Home-away patterns, breaks, non-consecutive rounds, complexity

Abstract:

In sports scheduling, a team is said to have a break when it plays two home (or two away) matches in a pair of consecutive rounds. In this paper, we generalize this concept by also considering pairs of nonconsecutive rounds. We show that a set of home-away patterns minimizing the number of generalized breaks cannot be found in polynomial time, unless P=NP. For the special case where all teams have the same set of breaks, the decision version becomes polynomially solvable; the optimization version remains NP-hard. For this special case, we also provide a lower bound for the number of generalized breaks for a given break set, thereby generalizing a classical result by De Werra.