Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments

Amelia Bădică, Costin Bădică, Ion Buligiu, Liviu Ion Ciora and Doina Logofătu
Additional contact information
Amelia Bădică: Department of Statistics and Business Informatics, University of Craiova, 200585 Craiova, Romania
Costin Bădică: Department of Computers and Information Technology, University of Craiova, 200585 Craiova, Romania
Ion Buligiu: Department of Statistics and Business Informatics, University of Craiova, 200585 Craiova, Romania
Liviu Ion Ciora: Department of Statistics and Business Informatics, University of Craiova, 200585 Craiova, Romania
Doina Logofătu: Faculty of Computer Science and Engineering, Frankfurt University of Applied Sciences, Nibelungenplatz 1, 60318 Frankfurt am Main, Germany

Mathematics, 2021, vol. 9, issue 19, 1-24

Abstract: We study competitions structured as hierarchically shaped single-elimination tournaments. We define optimal tournaments by maximizing attractiveness such that the topmost players will have the chance to meet in higher stages of the tournament. We propose a dynamic programming algorithm for computing optimal tournaments and we provide its sound complexity analysis. Based on the idea of the dynamic programming approach, we also develop more efficient deterministic and stochastic sub-optimal algorithms. We present experimental results obtained with the Python implementation of all the proposed algorithms regarding the optimality of solutions and the efficiency of the running time.

Keywords: optimization; knockout tournament; dynamic programming algorithm; computational complexity; combinatorics (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/19/2480/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/19/2480/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:19:p:2480-:d:649698

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().