The query complexity of a permutation-based variant of mastermind

DOI10.1016/j.dam.2019.01.007zbMath1411.91153arXiv1812.08480MaRDI 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 complexity; black-box complexity; \textsc{LeadingOnes}; hidden permutation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A46: Combinatorial games

91-04: Software, source code, etc. for problems pertaining to game theory, economics, and finance

Related Items

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

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