Breaks, cuts, and patterns |
| |
Authors: | Dries R Goossens Frits CR Spieksma |
| |
Institution: | aResearch Foundation - Flanders, Belgium;bCenter for Operations Research and Business Statistics (ORSTAT), Belgium;cFaculty of Business and Economics, K.U.Leuven, Belgium |
| |
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=NP. When all teams have the same break set, the decision version becomes easy; optimizing remains NP-hard. |
| |
Keywords: | Sport scheduling Home-away patterns Breaks Nonconsecutive rounds Complexity |
本文献已被 ScienceDirect 等数据库收录! |