Geodesic
Solving static permutation mastermind using \(O(n \log n)\) queries
The electronic journal of combinatorics, Tome 29 (2022) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Permutation Mastermind is a version of the classical mastermind game in which the number of positions $n$ is equal to the number of colors $k$, and repetition of colors is not allowed, neither in the codeword nor in the queries. In this paper we solve the main open question from Glazik, Jäger, Schiemann and Srivastav (2021), who asked whether their bound of $O(n^{1.525})$ for the static version can be improved to $O(n \log n)$, which would be best possible. By using a simple probabilistic argument we show that this is indeed the case.
DOI : 10.37236/10280
Classification : 91A46, 91A05, 05D40

Maxime Larcher  1   ; Anders Martinsson    ; Angelika Steger 

1 ETH Zürich 
@article{10_37236_10280,
     author = {Maxime Larcher and Anders Martinsson and Angelika Steger},
     title = {Solving static permutation mastermind using {\(O(n} \log n)\) queries},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {1},
     doi = {10.37236/10280},
     zbl = {1482.91054},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10280/}
}
TY  - JOUR
AU  - Maxime Larcher
AU  - Anders Martinsson
AU  - Angelika Steger
TI  - Solving static permutation mastermind using \(O(n \log n)\) queries
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10280/
DO  - 10.37236/10280
ID  - 10_37236_10280
ER  - 
%0 Journal Article
%A Maxime Larcher
%A Anders Martinsson
%A Angelika Steger
%T Solving static permutation mastermind using \(O(n \log n)\) queries
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10280/
%R 10.37236/10280
%F 10_37236_10280
Maxime Larcher; Anders Martinsson; Angelika Steger. Solving static permutation mastermind using \(O(n \log n)\) queries. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10280

Cité par Sources :