The unbiased black-box complexity of partition is polynomial

DOI10.1016/J.ARTINT.2014.07.009MaRDI QIDQ460634zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Timo Kötzing, Carola Doerr

Publication date 13 October 2014

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2014.07.009

zbMATH Keywords

heuristic searchevolutionary computationrun-time analysis

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of partition functions
• Automata, Languages and Programming
• scientific article; zbMATH DE number 6341750
• On the complexity of some partition problems
• A note on the complexity of a partition algorithm
• On the computational complexity of (O,P)-partition problems
• Parameterized complexity of satisfactory partition problem
• Parameterized complexity of satisfactory partition problem
• The black-box query complexity of polynomial summation
• Computing and Combinatorics

Cites work

• scientific article; zbMATH DE number 1566497 (Why is no real title available?)
• scientific article; zbMATH DE number 5572573 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• scientific article; zbMATH DE number 3194843 (Why is no real title available?)
• Analyzing evolutionary algorithms. The computer science perspective.
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Black-box complexities of combinatorial problems
• Black-box search by unbiased variation
• Faster black-box algorithms through higher arity operators
• Local optimization on graphs
• Lower bounds on the worst-case complexity of some oracle algorithms
• Memory-restricted black-box complexity of OneMax
• Minimization algorithms and random walk on the d-cube
• Oracles and queries that are sufficient for exact learning
• Queries and concept learning
• Ranking-based black-box complexity
• Reducibility among combinatorial problems
• Reducing the arity in unbiased black-box complexity
• STACS 2005
• The query complexity of finding a hidden permutation
• The rate of convergence to optimality of the LPT rule
• Upper and lower bounds for randomized search heuristics in black-box optimization

Cited in

(4)

• Black-box search by unbiased variation
• Black-box complexities of combinatorial problems
• Reducing the arity in unbiased black-box complexity
• Unbiasedness of estimation-of-distribution algorithms

This page was built for publication: The unbiased black-box complexity of partition is polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q460634)