The query complexity of a permutation-based variant of mastermind

DOI10.1016/j.dam.2019.01.007zbMath1411.91153arXiv1812.08480OpenAlexW2904757015MaRDI QIDQ1741495

Kurt Mehlhorn, Manindra Agrawal, Peyman Afshani, Kasper Green Larsen, Benjamin Doerr, Carola Doerr

Publication date: 3 May 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.08480

zbMATH Keywords

query complexityblack-box complexity\textsc{LeadingOnes}hidden permutation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial games (91A46) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Related Items

Unnamed Item, Choosing the right algorithm with hints from complexity theory, The exact query complexity of yes-no permutation mastermind, The runtime of the compact genetic algorithm on jump functions, Working principles of binary differential evolution, Mutation Rate Control in the $$(1+\lambda )$$ Evolutionary Algorithm with a Self-adjusting Lower Bound, Quantum algorithm for learning secret strings and its experimental demonstration

Cites Work

• Unnamed Item
• Mastermind
• On the analysis of the \((1+1)\) evolutionary algorithm
• The \((1+1)\) elitist black-box complexity of LeadingOnes
• Black-box search by unbiased variation
• Upper and lower bounds for randomized search heuristics in black-box optimization
• The Query Complexity of Finding a Hidden Permutation
• Playing Mastermind With Many Colors
• The Complexity of Enumeration and Reliability Problems
• Faster black-box algorithms through higher arity operators