Single elimination tournament design using dynamic programming algorithm
DOI:
https://doi.org/10.30812/matrik.v23i1.3290Keywords:
Algorithm, Dynamic Programming, Optimization, Single Elimination, TournamentAbstract
Finding the best single-elimination tournament design is important in scientific inquiry because it can have major financial implications for event organizers and participants. This research aims to create an optimal single-elimination tournament design using binary tree modeling with dummy techniques. Dynamic programming algorithms have been used to compute optimal single-elimination designs to overcome this effectively. This research method uses various implementations of sub-optimal algorithms and then compares their performance in terms of runtime and optimality as a solution to measure the comparison of sub-algorithms. This research shows that the difference in relative costs produced by various sub-algorithms with the same input is quite low. This is expected because quotes are generated as integer values from a small interval 1, ≤ 9, whereas costs tend to reach much higher values. From the comparison of these sub-algorithms, the best results among the sub-optimal algorithms were obtained in the Sub Optimal algorithm 3. We present the experimental findings achieved using the Python implementation of the suggested algorithm, with a focus on the best single-elimination tournament design solution.
Downloads
Download data is not yet available.
References
[1] P. Manurangsi and W. Suksompong, “Fixing Knockout Tournaments With Seeds,†IJCAI International Joint Conference on
Artificial Intelligence, pp. 412–418, 2022.
[2] M. P. Kim, W. Suksompong, and V. V. Williams, “Who Can Win a Single-Elimination Tournament?†pp. 1–13, 2018.
[3] L. Csat´o, “A simulation comparison of tournament designs for theWorld Men’s Handball Championships,†International Transactions
in Operational Research, vol. 28, no. 5, pp. 2377–2401, 2021.
[4] E. C. Olymphic, “New Study on the Economic impact of Sport released by the European Commission,†2020.
[5] R. Hulett, “Single-elimination brackets fail to approximate Copeland winner,†Leibniz International Proceedings in Informatics,
LIPIcs, vol. 145, no. 13, pp. 1–13, 2019.
[6] Y. Ikhwani, K. Marzuki, and A. Ramadhan, “Automated University Lecture Schedule Generator based on Evolutionary Algorithm,â€
vol. 22, no. 1, pp. 127–136, 2022.
[7] J. Kuo and J. W. Sheppard, “Tournament Topology Particle Swarm Optimization,†2021 IEEE Congress on Evolutionary Computation,
CEC 2021 - Proceedings, pp. 2265–2272, 2021.
[8] F. Spieksma, R. Pendavingh, and R. Lambers, “How to Design a Stable Serial Knockout Competition,†2022.
[9] K. Gokcesu and H. Gokcesu, “Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament
Design,†pp. 1–6, 2022.
[10] D. B˘adic˘a, A., B˘adic˘a, C., Buligiu, I., Ciora, L.I., Logoftu, “Optimal Knockout Tournaments: Definition and Computation,†in
International Conference on Large-Scale Scientific Computing, 2022.
[11] F. Della Croce, G. Dragotto, and R. Scatamacchia, “On fairness and diversification in WTA and ATP tennis tournaments generation,â€
Annals of Operations Research, vol. 316, no. 2, pp. 1107–1119, 2022.
[12] J. Guyon, “Choose your opponent: A new knockout design for hybrid tournaments,†Journal of Sports Analytics, vol. 8, no. 1,
pp. 9–29, 2021.
[13] H. Aziz, S. Gaspers, S. Mackenzie, N. Mattei, P. Stursberg, and T. Walsh, “Fixing balanced knockout and double elimination
tournaments,†Artificial Intelligence, vol. 262, no. May, pp. 1–14, 2018.
[14] A. Karpov, “Generalized knockout tournament seedings,†International Journal of Computer Science in Sport, vol. 17, no. 2,
pp. 113–127, 2018.
[15] P. Bhumipol, N. Makaje, T. Kawjaratwilai, and R. Ruangthai, “Match analysis of professional Muay Thai fighter between
winner and loser,†Journal of Human Sport and Exercise, vol. 18, no. 3, pp. 657–669, 2023.
[16] B. R. Sziklai, P. Bir´o, and L. Csat´o, “The efficacy of tournament designs,†Computers and Operations Research, vol. 144, no.
February, 2022.
[17] T. Stojadinovi´c, “On catalan numbers,†Teaching of Mathematics, vol. 18, no. 1, pp. 16–24, 2015.
[18] O. Banias, “Test case selection-prioritization approach based on memoization dynamic programming algorithm,†Information
and Software Technology, vol. 115, no. June, pp. 119–130, 2019.
[19] A. B˘adic˘a, C. B˘adic˘a, I. Buligiu, L. I. Ciora, and D. Logoftu, “Dynamic programming algorithms for computing optimal
knockout tournaments,†Mathematics, vol. 9, no. 19, 2021.
[20] D. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, part 1 ed. Boston: Addison-Wesley
Professional, 2011.
Artificial Intelligence, pp. 412–418, 2022.
[2] M. P. Kim, W. Suksompong, and V. V. Williams, “Who Can Win a Single-Elimination Tournament?†pp. 1–13, 2018.
[3] L. Csat´o, “A simulation comparison of tournament designs for theWorld Men’s Handball Championships,†International Transactions
in Operational Research, vol. 28, no. 5, pp. 2377–2401, 2021.
[4] E. C. Olymphic, “New Study on the Economic impact of Sport released by the European Commission,†2020.
[5] R. Hulett, “Single-elimination brackets fail to approximate Copeland winner,†Leibniz International Proceedings in Informatics,
LIPIcs, vol. 145, no. 13, pp. 1–13, 2019.
[6] Y. Ikhwani, K. Marzuki, and A. Ramadhan, “Automated University Lecture Schedule Generator based on Evolutionary Algorithm,â€
vol. 22, no. 1, pp. 127–136, 2022.
[7] J. Kuo and J. W. Sheppard, “Tournament Topology Particle Swarm Optimization,†2021 IEEE Congress on Evolutionary Computation,
CEC 2021 - Proceedings, pp. 2265–2272, 2021.
[8] F. Spieksma, R. Pendavingh, and R. Lambers, “How to Design a Stable Serial Knockout Competition,†2022.
[9] K. Gokcesu and H. Gokcesu, “Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament
Design,†pp. 1–6, 2022.
[10] D. B˘adic˘a, A., B˘adic˘a, C., Buligiu, I., Ciora, L.I., Logoftu, “Optimal Knockout Tournaments: Definition and Computation,†in
International Conference on Large-Scale Scientific Computing, 2022.
[11] F. Della Croce, G. Dragotto, and R. Scatamacchia, “On fairness and diversification in WTA and ATP tennis tournaments generation,â€
Annals of Operations Research, vol. 316, no. 2, pp. 1107–1119, 2022.
[12] J. Guyon, “Choose your opponent: A new knockout design for hybrid tournaments,†Journal of Sports Analytics, vol. 8, no. 1,
pp. 9–29, 2021.
[13] H. Aziz, S. Gaspers, S. Mackenzie, N. Mattei, P. Stursberg, and T. Walsh, “Fixing balanced knockout and double elimination
tournaments,†Artificial Intelligence, vol. 262, no. May, pp. 1–14, 2018.
[14] A. Karpov, “Generalized knockout tournament seedings,†International Journal of Computer Science in Sport, vol. 17, no. 2,
pp. 113–127, 2018.
[15] P. Bhumipol, N. Makaje, T. Kawjaratwilai, and R. Ruangthai, “Match analysis of professional Muay Thai fighter between
winner and loser,†Journal of Human Sport and Exercise, vol. 18, no. 3, pp. 657–669, 2023.
[16] B. R. Sziklai, P. Bir´o, and L. Csat´o, “The efficacy of tournament designs,†Computers and Operations Research, vol. 144, no.
February, 2022.
[17] T. Stojadinovi´c, “On catalan numbers,†Teaching of Mathematics, vol. 18, no. 1, pp. 16–24, 2015.
[18] O. Banias, “Test case selection-prioritization approach based on memoization dynamic programming algorithm,†Information
and Software Technology, vol. 115, no. June, pp. 119–130, 2019.
[19] A. B˘adic˘a, C. B˘adic˘a, I. Buligiu, L. I. Ciora, and D. Logoftu, “Dynamic programming algorithms for computing optimal
knockout tournaments,†Mathematics, vol. 9, no. 19, 2021.
[20] D. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, part 1 ed. Boston: Addison-Wesley
Professional, 2011.
Downloads
Published
2023-11-20
Issue
Section
Articles
How to Cite
[1]
yusri ikhwani, A. Ramadhan, M. Bahit, and T. H. Faesal, “Single elimination tournament design using dynamic programming algorithm”, MATRIK, vol. 23, no. 1, pp. 113–130, Nov. 2023, doi: 10.30812/matrik.v23i1.3290.
Similar Articles
- Tb Ai Munandar, Ajif Yunizar Yusuf Pratama, Regional Clustering Based on Types of Non-Communicable Diseases Using k-Means Algorithm , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 23 No. 2 (2024)
- Zein Zein, Ahmat Adil, APLIKASI MEDIA BANTU PEMBELAJARAN KRIPTOGRAFI DENGAN MENGGUNAKAN ALGORITMA MESSAGE DIGEST 5 (MD5) , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 15 No. 2 (2016)
- Ahmad Fatoni Dwi Putra, Muhamad Nizam Azmi, Heri Wijayanto, Satria Utama, I Gede Putu Wirarama Wedashwara Wirawan, Optimizing Rain Prediction Model Using Random Forest and Grid Search Cross-Validation for Agriculture Sector , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 23 No. 3 (2024)
- Imanuddin Imanuddin, Fachrid Alhadi, Raza Oktafian, Ahmad Ihsan, Deteksi Mata Mengantuk pada Pengemudi Mobil Menggunakan Metode Viola Jones , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 18 No. 2 (2019)
- Rendy Rian Chrisna Putra, Tri Sugihartono, Penerapan Algoritma Fisher-Yates Shuffle pada Computer Based Test Ujian Sekolah di SMKN 1 Payung , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 18 No. 2 (2019)
- Abd Mizwar A Rahim, Andi Sunyoto, Muhammad Rudyanto Arief, Stroke Prediction Using Machine Learning Method with Extreme Gradient Boosting Algorithm , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 21 No. 3 (2022)
- Imam Riadi, Herman Herman, Fitriah Fitriah, Suprihatin Suprihatin, Optimizing Inventory with Frequent Pattern Growth Algorithm for Small and Medium Enterprises , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 23 No. 1 (2023)
- Raisul Azhar, Kurniawan Kurniawan, APLIKASI KEAMANAN SMS MENGGUNAKAN ALGORITMA RIJNDAEL , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 16 No. 1 (2016)
- Syafri Arlis, Muhammad Reza Putra, Musli Yanto, Improved Image Segmentation using Adaptive Threshold Morphology on CT-Scan Images for Brain Tumor Detection , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 23 No. 3 (2024)
- Saiful Nur Arif, Muhammad Dahria, Sarjon Defit, Dicky Novriansyah, Ali Ikhwan, Implementation of Single Linked on Machine Learning for Clustering Student Scientific Fields , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 22 No. 1 (2022)
You may also start an advanced similarity search for this article.
Most read articles by the same author(s)
- yusri ikhwani, Khairan Marzuki, As’ary Ramadhan, Automated University Lecture Schedule Generator based on Evolutionary Algorithm , MATRIK : Jurnal Manajemen, Teknik Informatika dan Rekayasa Komputer: Vol. 22 No. 1 (2022)
.png)
