Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint

DOI10.1007/s00453-020-00779-3OpenAlexW3097407191MaRDI QIDQ2240133

Mojgan Pourhassan, Carsten Witt, Frank Neumann

Publication date: 5 November 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

constraintslinear functionsruntime analysis\((1+1)\) EArandomised search heuristics

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Analyzing evolutionary algorithms. The computer science perspective.
• Computing minimum cuts by randomized search heuristics
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Evolutionary algorithms and matroid optimization problems
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• On the analysis of the \((1+1)\) evolutionary algorithm
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Adaptive drift analysis
• Multiplicative drift analysis
• Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints
• Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• On the size of weights in randomized search heuristics
• When do evolutionary algorithms optimize separable functions in parallel?

This page was built for publication: Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint