Runtime analysis of RLS and \((1 + 1)\) EA for the dynamic weighted vertex cover problem

DOI10.1016/J.TCS.2019.03.003zbMath1443.68229arXiv1903.02195OpenAlexW2963353311MaRDI QIDQ2182716

Vahid Roostapour, Frank Neumann, Mojgan Pourhassan

Publication date: 26 May 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

local searchcombinatorial optimisationweighted vertex cover problem\((1 + 1)\) EAdynamic vertex cover problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (4)

Exponential upper bounds for the runtime of randomized search heuristics ⋮ Runtime analysis of the \((\mu + 1)\)-EA on the dynamic BinVal function ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem ⋮ Pareto optimization for subset selection with dynamic cost constraints

Cites Work

• Unnamed Item
• Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change
• Fixed-parameter evolutionary algorithms and the vertex cover problem
• (1+1) EA on Generalized Dynamic OneMax
• Tight Bounds for Blind Search on the Integers and the Reals
• Approximating vertex cover using edge-based representations
• On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms
• Introduction to evolutionary computing

This page was built for publication: Runtime analysis of RLS and \((1 + 1)\) EA for the dynamic weighted vertex cover problem