Concentration of first hitting times under additive drift

DOI10.1007/S00453-015-0048-0zbMath1348.68229OpenAlexW4379365767MaRDI QIDQ306489

Timo Kötzing

Publication date: 31 August 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0048-0

zbMATH Keywords

concentrationadditive driftruntime analysis

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (18)

Tail bounds on hitting times of randomized search heuristics using variable drift analysis ⋮ Concentration of first hitting times under additive drift ⋮ Drift Analysis and Evolutionary Algorithms Revisited ⋮ Does comma selection help to cope with local optima? ⋮ Fixed-target runtime analysis ⋮ The complex parameter landscape of the compact genetic algorithm ⋮ Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem ⋮ Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints ⋮ Self-adjusting population sizes for the (1,\( \lambda )\)-EA on monotone functions ⋮ Runtime Analysis of a Co-Evolutionary Algorithm ⋮ OneMax is not the easiest function for fitness improvements ⋮ Unnamed Item ⋮ Two-dimensional drift analysis: optimizing two functions simultaneously can be hard ⋮ Multiplicative up-drift ⋮ Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions ⋮ Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming ⋮ The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time ⋮ First-hitting times under drift

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Concentration of first hitting times under additive drift
• Hoeffding's inequality for supermartingales
• Simplified drift analysis for proving lower bounds in evolutionary computation
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Adaptive drift analysis
• Multiplicative drift analysis
• On the runtime analysis of the simple genetic algorithm
• Exponential inequalities for martingales with applications
• Weighted sums of certain dependent random variables
• 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
• Concentration of Measure for the Analysis of Randomized Algorithms
• Sub-Gaussian random variables

This page was built for publication: Concentration of first hitting times under additive drift