An Optimal Algorithm for Finding Champions in Tournament Graphs
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
An Optimal Algorithm for Finding Champions in Tournament Graphs. / Beretta, Lorenzo; Nardini, Franco Maria; Trani, Roberto; Venturini, Rossano.
In: IEEE Transactions on Knowledge and Data Engineering, Vol. 35, No. 10, 2023, p. 10197-10209.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - An Optimal Algorithm for Finding Champions in Tournament Graphs
AU - Beretta, Lorenzo
AU - Nardini, Franco Maria
AU - Trani, Roberto
AU - Venturini, Rossano
N1 - Publisher Copyright: © 1989-2012 IEEE.
PY - 2023
Y1 - 2023
N2 - A tournament graph is a complete directed graph, which can be used to model a round-robin tournament between n players. In this paper, we address the problem of finding a champion of the tournament, also known as Copeland winner, which is a player that wins the highest number of matches. In detail, we aim to investigate algorithms that find the champion by playing a low number of matches. Solving this problem allows us to speed up several Information Retrieval and Recommender System applications, including question answering, conversational search, etc. Indeed, these applications often search for the champion inducing a round-robin tournament among the players by employing a machine learning model to estimate who wins each pairwise comparison. Our contribution, thus, allows finding the champion by performing a low number of model inferences. We prove that any deterministic or randomized algorithm finding a champion with constant success probability requires Ω(ℓn) comparisons, where ℓ is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing ℓ, and we extend our analysis to three variants of the problem. Lastly, we conduct a comprehensive experimental assessment of the proposed algorithms on a question answering task on public data. Results show that our proposed algorithms speed up the retrieval of the champion up to 13× with respect to the state-of-the-art algorithm that perform the full tournament.
AB - A tournament graph is a complete directed graph, which can be used to model a round-robin tournament between n players. In this paper, we address the problem of finding a champion of the tournament, also known as Copeland winner, which is a player that wins the highest number of matches. In detail, we aim to investigate algorithms that find the champion by playing a low number of matches. Solving this problem allows us to speed up several Information Retrieval and Recommender System applications, including question answering, conversational search, etc. Indeed, these applications often search for the champion inducing a round-robin tournament among the players by employing a machine learning model to estimate who wins each pairwise comparison. Our contribution, thus, allows finding the champion by performing a low number of model inferences. We prove that any deterministic or randomized algorithm finding a champion with constant success probability requires Ω(ℓn) comparisons, where ℓ is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing ℓ, and we extend our analysis to three variants of the problem. Lastly, we conduct a comprehensive experimental assessment of the proposed algorithms on a question answering task on public data. Results show that our proposed algorithms speed up the retrieval of the champion up to 13× with respect to the state-of-the-art algorithm that perform the full tournament.
KW - copeland winner
KW - minimum selection
KW - pairwise ranking
KW - round-robin tournament
KW - Tournament graph
U2 - 10.1109/TKDE.2023.3267345
DO - 10.1109/TKDE.2023.3267345
M3 - Journal article
AN - SCOPUS:85153493799
VL - 35
SP - 10197
EP - 10209
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
SN - 1041-4347
IS - 10
ER -
ID: 389673494