Fixing a Balanced Knockout Tournament
Authors: Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, Toby Walsh
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner. |
| Researcher Affiliation | Collaboration | Haris Aziz and Serge Gaspers and Simon Mackenzie and Nicholas Mattei NICTA and UNSW, Sydney, Australia {haris.aziz, serge.gaspers, simon.mackenzie, nicholas.mattei}@nicta.com.au Paul Stursberg Technische Universit at M unchen, Germany paul.stursberg@ma.tum.de Toby Walsh NICTA and UNSW, Sydney, Australia toby.walsh@nicta.com.au |
| Pseudocode | No | The paper describes algorithmic approaches verbally and mathematically, but it does not include a formally structured pseudocode block or an algorithm listing. |
| Open Source Code | No | The paper does not contain any statement about making its source code publicly available, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper does not mention using any publicly available datasets for training or evaluation. It defines abstract player sets and pairwise comparison matrices for its theoretical problem formulation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical data splits for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., CPU, GPU models) used for computation or analysis. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers (e.g., programming languages, libraries, or solvers with their specific versions). |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity and algorithm design. It does not describe an experimental setup with hyperparameters, training configurations, or system-level settings. |