Sorting by swaps with noisy comparisons

DOI10.1007/s00453-018-0429-2zbMath1411.68145arXiv1803.04509OpenAlexW2791077206MaRDI QIDQ1725654

Barbara Geissmann, Tomáš Gavenčiak, Johannes Lengler

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

noisesortingevolutionary algorithmsoptimization heuristicscomparison-basedrandom swaps

Mathematics Subject Classification ID

Searching and sorting (68P10) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Runtime analysis for permutation-based evolutionary algorithms, Sorting by swaps with noisy comparisons, Optimal dislocation with persistent errors in subquadratic time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithm portfolios for noisy optimization
• Robustness of populations in stochastic environments
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Analysis of runtime of optimization algorithms for noisy functions over discrete codomains
• Simple and cumulative regret for continuous noisy optimization
• Asymptotics in ASEP with step initial condition
• Interaction of Markov processes
• Modeling genetic algorithms with Markov chains.
• Maximal total absolute displacement of a permutation
• Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practise.
• Sorting by swaps with noisy comparisons
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Populations can be essential in tracking dynamic optima
• (1+1) EA on Generalized Dynamic OneMax
• Evolution Strategies with Additive Noise
• Fault Tolerant Sorting Networks
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• Advances in Artificial Intelligence – SBIA 2004
• Approximate Sorting