### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Universiteit Twente |

Number of pages | 9 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 1999 |

### Publication series

Name | Memorandum / Faculty of Mathematical Sciences |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1505 |

ISSN (Print) | 0169-2690 |

### Keywords

- MSC-03D15
- EWI-3325
- IR-65693
- METIS-141287
- MSC-90C27

### Cite this

*The new FIFA rules are hard: Complexity aspects of sports competitions*. (Memorandum / Faculty of Mathematical Sciences; No. 1505). Enschede: Universiteit Twente.

}

*The new FIFA rules are hard: Complexity aspects of sports competitions*. Memorandum / Faculty of Mathematical Sciences, no. 1505, Universiteit Twente, Enschede.

**The new FIFA rules are hard: Complexity aspects of sports competitions.** / Kern, Walter; Paulusma, Daniël.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - The new FIFA rules are hard: Complexity aspects of sports competitions

AU - Kern, Walter

AU - Paulusma, Daniël

N1 - Imported from MEMORANDA

PY - 1999

Y1 - 1999

N2 - Consider a soccer 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 complexity of this question depends on the way scores are allocated according to the outcome of a match. For example, the problem is polynomially solvable for the ancient FIFA rules (2:0 resp. 1:1) but becomes NP-hard if the new rules (3:0 resp. 1:1) are applied. We determine the complexity of the above problem for all possible score allocation rules.

AB - Consider a soccer 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 complexity of this question depends on the way scores are allocated according to the outcome of a match. For example, the problem is polynomially solvable for the ancient FIFA rules (2:0 resp. 1:1) but becomes NP-hard if the new rules (3:0 resp. 1:1) are applied. We determine the complexity of the above problem for all possible score allocation rules.

KW - MSC-03D15

KW - EWI-3325

KW - IR-65693

KW - METIS-141287

KW - MSC-90C27

M3 - Report

SN - 0169-2690

T3 - Memorandum / Faculty of Mathematical Sciences

BT - The new FIFA rules are hard: Complexity aspects of sports competitions

PB - Universiteit Twente

CY - Enschede

ER -