Breaks, cuts, and patterns

D.R. Goossens, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)428-432
JournalOperations Research Letters
Volume39
Issue number6
DOIs
Publication statusPublished - Nov 2011
Externally publishedYes

Keywords

  • Sport scheduling
  • Home-away patterns
  • Breaks
  • Nonconsecutive rounds
  • Complexity

Cite this