Paper Info
Title
Sports scheduling with generalized breaks
Abstract
In sports scheduling, a team is said to have a break when it plays two home (or two away) matches in consecutive rounds. In this paper, we generalize this concept by also considering pairs of nonconsecutive rounds. We determine the complexity of the problem of finding a set of home-away patterns minimizing the number of generalized breaks when a so-called break set is given. Although the decision version of this problem can be solved in polynomial time, the optimization version turns out to be NP-hard. We also provide a lower bound for the number of generalized breaks for a given break set, and generalize a classic result by De Werra. We illustrate the relevance of generalized breaks with practical applications from, amongst others, the Belgian football league.
Year
DOI
Venue
2011
10.1109/SCIS.2011.5976546
Computational Intelligence in Scheduling
Keywords
Field
DocType
computational complexity,scheduling,sport,Belgian football league,NP-hard,break set,generalized breaks,home-away patterns,nonconsecutive rounds,polynomial time,sports scheduling
Football,Mathematical optimization,Mathematical economics,Polynomial,Computer science,Scheduling (computing),Upper and lower bounds,Algorithm,Schedule,Time complexity,Computational complexity theory
Conference
ISBN
Citations 
PageRank 
978-1-61284-195-3
0
0.34
References 
Authors
5
2
Name
Order
Citations
PageRank
Dries R. Goossens112915.88
Frits C. R. Spieksma259158.84