Breaks, cuts, and patterns

D.R. Goossens; F.C.R. Spieksma

doi:10.1016/j.orl.2011.09.001

Breaks, cuts, and patterns

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

Research output: Contribution to journal › Article › Academic › peer-review

12 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 language	English
Pages (from-to)	428-432
Journal	Operations Research Letters
Volume	39
Issue number	6
DOIs	https://doi.org/10.1016/j.orl.2011.09.001
Publication status	Published - Nov 2011
Externally published	Yes

Keywords

Sport scheduling
Home-away patterns
Breaks
Nonconsecutive rounds
Complexity

Access to Document

10.1016/j.orl.2011.09.001

Cite this

@article{6974db90de0c450996e61c56d0152d4e,

title = "Breaks, cuts, and patterns",

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",

author = "D.R. Goossens and F.C.R. Spieksma",

year = "2011",

month = nov,

doi = "10.1016/j.orl.2011.09.001",

language = "English",

volume = "39",

pages = "428--432",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Breaks, cuts, and patterns

AU - Goossens, D.R.

AU - Spieksma, F.C.R.

PY - 2011/11

Y1 - 2011/11

N2 - 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.

AB - 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.

KW - Sport scheduling

KW - Home-away patterns

KW - Breaks

KW - Nonconsecutive rounds

KW - Complexity

U2 - 10.1016/j.orl.2011.09.001

DO - 10.1016/j.orl.2011.09.001

M3 - Article

SN - 0167-6377

VL - 39

SP - 428

EP - 432

JO - Operations Research Letters

JF - Operations Research Letters

IS - 6

ER -

Breaks, cuts, and patterns

Abstract

Keywords

Access to Document

Fingerprint

Cite this