| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143249 | Operations Research Letters | 2011 | 5 Pages |
Abstract
We generalize the concept of a break by considering pairs of arbitrary rounds. We show that a set of home-away patterns minimizing the number of generalized breaks cannot be found in polynomial time, unless P=NPP=NP. When all teams have the same break set, the decision version becomes easy; optimizing remains NP-hard.
► The concept of a break is generalized by considering pairs of arbitrary rounds. ► Finding a set of home-away patterns minimizing the number of breaks is NP-hard. ► In case of identical break sets, the decision version becomes easy.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dries R. Goossens, Frits C.R. Spieksma,