Skip to main content

Research Repository

Advanced Search

The computational complexity of the elimination problem in generalized sports competitions

Kern, W.; Paulusma, D.

Authors

W. Kern



Abstract

Consider a sports competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to win the competition. The computational complexity of this question depends on the way scores are allocated according to the outcome of a match. For competitions with at most 3 different outcomes of a match the complexity is already known. In practice there are many competitions in which more than 3 outcomes are possible. We determine the complexity of the above problem for competitions with an arbitrary number of different outcomes. Our model also includes competitions that are asymmetric in the sense that away playing teams possibly receive other scores than home playing teams.

Citation

Kern, W., & Paulusma, D. (2004). The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1(2), 205-214. https://doi.org/10.1016/j.disopt.2003.12.003

Journal Article Type Article
Publication Date 2004-11
Deposit Date Apr 23, 2008
Journal Discrete Optimization
Print ISSN 1572-5286
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 1
Issue 2
Pages 205-214
DOI https://doi.org/10.1016/j.disopt.2003.12.003
Keywords Elimination problem, NP-complete, Network flow.
Public URL https://durham-repository.worktribe.com/output/1576223