Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/19/2480 |
| _version_ | 1797515984508026880 |
|---|---|
| author | Amelia Bădică Costin Bădică Ion Buligiu Liviu Ion Ciora Doina Logofătu |
| author_facet | Amelia Bădică Costin Bădică Ion Buligiu Liviu Ion Ciora Doina Logofătu |
| author_sort | Amelia Bădică |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T06:54:54Z |
| format | Article |
| id | doaj.art-4ff526af19004382ac37b991fe724ca5 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T06:54:54Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-4ff526af19004382ac37b991fe724ca52023-11-22T16:30:58ZengMDPI AGMathematics2227-73902021-10-01919248010.3390/math9192480Dynamic Programming Algorithms for Computing Optimal Knockout TournamentsAmelia Bădică0Costin Bădică1Ion Buligiu2Liviu Ion Ciora3Doina Logofătu4Department of Statistics and Business Informatics, University of Craiova, 200585 Craiova, RomaniaDepartment of Computers and Information Technology, University of Craiova, 200585 Craiova, RomaniaDepartment of Statistics and Business Informatics, University of Craiova, 200585 Craiova, RomaniaDepartment of Statistics and Business Informatics, University of Craiova, 200585 Craiova, RomaniaFaculty of Computer Science and Engineering, Frankfurt University of Applied Sciences, Nibelungenplatz 1, 60318 Frankfurt am Main, GermanyWe 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.https://www.mdpi.com/2227-7390/9/19/2480optimizationknockout tournamentdynamic programming algorithmcomputational complexitycombinatorics |
| spellingShingle | Amelia Bădică Costin Bădică Ion Buligiu Liviu Ion Ciora Doina Logofătu Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments Mathematics optimization knockout tournament dynamic programming algorithm computational complexity combinatorics |
| title | Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments |
| title_full | Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments |
| title_fullStr | Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments |
| title_full_unstemmed | Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments |
| title_short | Dynamic Programming Algorithms for Computing Optimal Knockout Tournaments |
| title_sort | dynamic programming algorithms for computing optimal knockout tournaments |
| topic | optimization knockout tournament dynamic programming algorithm computational complexity combinatorics |
| url | https://www.mdpi.com/2227-7390/9/19/2480 |
| work_keys_str_mv | AT ameliabadica dynamicprogrammingalgorithmsforcomputingoptimalknockouttournaments AT costinbadica dynamicprogrammingalgorithmsforcomputingoptimalknockouttournaments AT ionbuligiu dynamicprogrammingalgorithmsforcomputingoptimalknockouttournaments AT liviuionciora dynamicprogrammingalgorithmsforcomputingoptimalknockouttournaments AT doinalogofatu dynamicprogrammingalgorithmsforcomputingoptimalknockouttournaments |