<abstract xmlns="http://www.w3.org/1999/xhtml"><p> Let n and k be integers such that n ≥ 2 and 1 ≤ k ≤n. In this paper, we consider the problem of finding an ordered list of the k best players out of n participants by organizing a tournament of rounds of pairwise matches (comparisons). Assuming that (i) in each match there is a winner (no ties) (ii) the relative strength of the players is constant throughout the tournament and (iii) the players’ strengths are transitive, the problem is equivalent to partially sorting n different, comparable objects, allowing parallelization in rounds. The rounds are restricted as one player can only play one match in each round. We propose concrete pairing algorithms and make conjectures about their performance in terms of the worst case number of rounds and matches required. The research article was started by professor Antal Iványi who sadly passed away during the work and was completed in his honor by the co-author. He hopes, in this modest way, to reflect his deep admiration for professor Iványi’s many contributions to the theory, practice and appreciation of algorithm design and analysis. </p></abstract>

Let n and k be integers such that n ≥ 2 and 1 ≤ k ≤n. In this paper, we consider the problem of finding an ordered list of the k best players out of n participants by organizing a tournament of rounds of pairwise matches (comparisons). Assuming that (i) in each match there is a winner (no ties) (ii) the relative strength of the players is constant throughout the tournament and (iii) the players’ strengths are transitive, the problem is equivalent to partially sorting n different, comparable objects, allowing parallelization in rounds. The rounds are restricted as one player can only play one match in each round. We propose concrete pairing algorithms and make conjectures about their performance in terms of the worst case number of rounds and matches required. The research article was started by professor Antal Iványi who sadly passed away during the work and was completed in his honor by the co-author. He hopes, in this modest way, to reflect his deep admiration for professor Iványi’s many contributions to the theory, practice and appreciation of algorithm design and analysis.

On partial sorting in restricted rounds

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Dedicated to the memory of Antal Iványi

Let n and k be integers such that n ≥ 2 and 1 ≤ k ≤n. In this paper, we consider the problem of finding an ordered list of the k best players out of n...

On partial sorting in restricted rounds

Publié en ligne: 01 août 2017

Pages: 17 - 34

Reçu: 12 juin 2017

DOI: https://doi.org/10.1515/ausi-2017-0002

Mots clés
partial sorting, parallel sorting, tournament, pairing algorithm

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

On partial sorting in restricted rounds

Publié en ligne: 01 août 2017

Pages: 17 - 34

Reçu: 12 juin 2017

DOI: https://doi.org/10.1515/ausi-2017-0002

Mots cléspartial sorting, parallel sorting, tournament, pairing algorithm

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
partial sorting, parallel sorting, tournament, pairing algorithm