Tight bounds for break minimization in tournament scheduling

Andries E. Brouwer; Gerhard F. Post; Gerhard Woeginger

doi:10.1016/j.jcta.2007.10.002

Tight bounds for break minimization in tournament scheduling

Andries E. Brouwer, Gerhard F. Post, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

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

5 Citations (Scopus)

68 Downloads (Pure)

Abstract

We consider round-robin sports tournaments with $n$ teams and $n-1$ rounds. We construct an infinite family of opponent schedules for which every home-away assignment induces at least $n(n-2)/4$ breaks. This construction establishes a matching lower bound for a corresponding upper bound from the literature.

Original language	English
Pages (from-to)	1065-1068
Number of pages	4
Journal	Journal of combinatorial theory. Series A
Volume	115
Issue number	Supplement/6
DOIs	https://doi.org/10.1016/j.jcta.2007.10.002
Publication status	Published - 2008

Keywords

break minimization
Sports scheduling
sports tournament
Latin squares

Access to Document

10.1016/j.jcta.2007.10.002Licence: Other

postEtAlFinal published version, 89.2 KBLicence: Other

Cite this

@article{7e98eead5d1741ec9e2d15233b963998,

title = "Tight bounds for break minimization in tournament scheduling",

abstract = "We consider round-robin sports tournaments with $n$ teams and $n-1$ rounds. We construct an infinite family of opponent schedules for which every home-away assignment induces at least $n(n-2)/4$ breaks. This construction establishes a matching lower bound for a corresponding upper bound from the literature.",

keywords = "break minimization, Sports scheduling, sports tournament, Latin squares",

author = "Brouwer, {Andries E.} and Post, {Gerhard F.} and Gerhard Woeginger",

year = "2008",

doi = "10.1016/j.jcta.2007.10.002",

language = "English",

volume = "115",

pages = "1065--1068",

journal = "Journal of combinatorial theory. Series A",

issn = "0097-3165",

publisher = "Academic Press",

number = "Supplement/6",

}

TY - JOUR

T1 - Tight bounds for break minimization in tournament scheduling

AU - Brouwer, Andries E.

AU - Post, Gerhard F.

AU - Woeginger, Gerhard

PY - 2008

Y1 - 2008

N2 - We consider round-robin sports tournaments with $n$ teams and $n-1$ rounds. We construct an infinite family of opponent schedules for which every home-away assignment induces at least $n(n-2)/4$ breaks. This construction establishes a matching lower bound for a corresponding upper bound from the literature.

AB - We consider round-robin sports tournaments with $n$ teams and $n-1$ rounds. We construct an infinite family of opponent schedules for which every home-away assignment induces at least $n(n-2)/4$ breaks. This construction establishes a matching lower bound for a corresponding upper bound from the literature.

KW - break minimization

KW - Sports scheduling

KW - sports tournament

KW - Latin squares

U2 - 10.1016/j.jcta.2007.10.002

DO - 10.1016/j.jcta.2007.10.002

M3 - Article

VL - 115

SP - 1065

EP - 1068

JO - Journal of combinatorial theory. Series A

JF - Journal of combinatorial theory. Series A

SN - 0097-3165

IS - Supplement/6

ER -

Tight bounds for break minimization in tournament scheduling

Abstract

Keywords

Access to Document

Fingerprint

Cite this