<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

Published Online: Aug 01, 2017

Page range: 17 - 34

Received: Jun 12, 2017

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

Keywords
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

Published Online: Aug 01, 2017

Page range: 17 - 34

Received: Jun 12, 2017

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

Keywordspartial sorting, parallel sorting, tournament, pairing algorithm

© 2017

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

Keywords
partial sorting, parallel sorting, tournament, pairing algorithm