Tight bounds for break minimization in tournament scheduling

Brouwer, Andries E. and Post, Gerhard F. and Woeginger, Gerhard J. (2008) Tight bounds for break minimization in tournament scheduling. Journal of Combinatorial Theory, Series A, 115 (6). pp. 1065-1068. ISSN 0097-3165

PDF
Restricted to UT campus only: Request a copy
89Kb

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.
Item Type:	Article
Copyright:	© 2008 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62555
Official URL:	http://dx.doi.org/10.1016/j.jcta.2007.10.002
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page

Metis ID: 251215