Analysis of the $(1+1)$-EA for Finding Approximate Solutions to Vertex Cover Problems

No abstract is available for this paper.

• Publication year

  2009

• Venue

  IEEE Transactions on Evolutionary Computation

• Publication date

  2009-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TEVC.2009.2014362
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Design and Management of Complex Technical Processes and Systems by means of Computational Intelligence Methods Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

  2008cited by this paper
• UNIVERSITY OF DORTMUND REIHE COMPUTATIONAL INTELLIGENCE COLLABORATIVE RESEARCH CENTER 531 Design and Management of Complex Technical Processes and Systems by means of Computational Intelligence Methods Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

  2007influential reference
• Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results

  2007cited by this paper
• Finding large cliques in sparse semi-random graphs by simple randomized search heuristics

  2007cited by this paper
• Design and Management of Complex Technical Processes and Systems by means of Computational Intelligence Methods On Improving Approximate Solutions by Evolutionary Algorithms

  2007cited by this paper
• Evolutionary algorithms and the Vertex Cover problem

  2007cited by this paper
• UNIVERSITY OF DORTMUND REIHE COMPUTATIONAL INTELLIGENCE COLLABORATIVE RESEARCH CENTER 531 Design and Management of Complex Technical Processes and Systems by means of Computational Intelligence Methods Evolutionary Algorithms and the Maximum Matching Problem

  2006influential reference
• A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem

  2005cited by this paper
• On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions

  2005cited by this paper
• Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics

  2005cited by this paper
• A study of drift analysis for estimating computation time of evolutionary algorithms

  2004cited by this paper
• Time complexity analysis of an evolutionary algorithm for finding nearly maximum cardinality matching

  2004cited by this paper
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem

  2004cited by this paper
• Towards an analytic framework for analysing the computation time of evolutionary algorithms

  2003cited by this paper
• Evolutionary Optimization

  2002cited by this paper
• On the analysis of the (1+1) evolutionary algorithm

  2002cited by this paper
• Introduction to algorithms [2nd ed.]

  2001cited by this paper
• Introduction to Algorithms, 2nd edition.

  2001cited by this paper
• Design and Management of Complex Technical Processes and Systems by means of Computational Intelligence Methods Evolutionary Algorithms-How to Cope With Plateaus of Constant Fitness and When to Reject Strings of the Same Fitness

  2001cited by this paper
• Design and Management of Complex Technical Processes and Systems by means of Computational Intelligence Methods Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions

  2001cited by this paper
• Drift analysis and average time complexity of evolutionary algorithms

  2001influential reference
• Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs

  2000cited by this paper
• On the Optimization of Unimodal Functions with the (1 + 1) Evolutionary Algorithm

  1998cited by this paper
• Evolutionary Algorithms for Vertex Cover

  1998cited by this paper
• Finite Markov Chain Results in Evolutionary Computation: A Tour d'Horizon

  1998influential reference
• A Rigorous Complexity Analysis of the (1 + 1) Evolutionary Algorithm for Separable Functions with Boolean Inputs

  1998cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Randomized algorithms

  1995influential reference
• A First Look at Graph Theory

  1991cited by this paper
• The time complexity of maximum matching by simulated annealing

  1988cited by this paper
• Combinatorial optimization:Algorithms and complexity

  1984influential reference
• Hitting-time and occupation-time bounds implied by drift analysis with applications

  1982cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper
• Graph theory

  1969cited by this paper

• An improved quantum-inspired evolutionary algorithm framework implemented to solve minimum vertex cover problem

  2025cites this paper
• Running-time Analysis of ($\mu+\lambda$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation

  2025cites this paper
• A Distributed Symmetric Game Optimization to 3-Path Vertex Cover of Networks

  2025cites this paper
• Vertex Cover of Networks and Its Related Optimization Problems: An Overview

  2024cites this paper
• Yet Another Self-Stabilizing Minimum Vertex Cover of a Network With Stochastic Stability

  2024cites this paper
• Probability weighting effect in vertex cover of networks via prospect-theoretic learning

  2023cites this paper
• A Gentle Introduction to Theory (for Non-Theoreticians)

  2023cites this paper
• Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

  2023cites this paper
• The $(1+(\lambda,\lambda))$ Genetic Algorithm on the Vertex Cover Problem: Crossover Helps Leaving Plateaus

  2022influential citation
• Adaptive Vertex Cover of Dynamical Networks With Prospect Theoretic Perspective

  2022cites this paper
• Theoretical analysis of garden balsam optimization algorithm

  2022cites this paper
• Analysis of a gray-box operator for vertex cover

  2022cites this paper
• Toward the minimum vertex cover of complex networks using distributed potential games

  2022cites this paper
• Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem

  2022cites this paper
• A gentle introduction to theory (for non-theoreticians)

  2022cites this paper
• Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems

  2022cites this paper
• On Performance of a Simple Multi-objective Evolutionary Algorithm on the Constrained Minimum Spanning Tree Problem

  2022cites this paper
• A population-based game-theoretic optimizer for the minimum weighted vertex cover

  2021cites this paper
• A gentle introduction to theory (for non-theoreticians)

  2021cites this paper
• The lower bounds on the runtime of the (1 + (λ, λ)) GA on the minimum spanning tree problem

  2021cites this paper
• A Genetic Algorithm for the Minimum Vertex Cover Problem with Interval-Valued Fitness

  2021cites this paper
• Time Complexity Analysis of Evolutionary Algorithms for 2-Hop (1, 2)-Minimum Spanning Tree Problem

  2021cites this paper
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems

  2021cites this paper
• Fast Immune System-Inspired Hypermutation Operators for Combinatorial Optimization

  2020cites this paper
• A gentle introduction to theory (for non-theoreticians)

  2020cites this paper
• Theory of Evolutionary Computation: Recent Developments in Discrete Optimization

  2020influential citation
• An improved (1+1) evolutionary algorithm for k-median clustering problem with performance guarantee

  2020cites this paper
• An Evolutionary Approach to Optimizing Teleportation Cost in Distributed Quantum Computation

  2020cites this paper
• Runtime Analysis of RLS and (1+1) EA for the Dynamic Weighted Vertex Cover Problem

  2019cites this paper
• An Evolutionary Approach to Optimizing Communication Cost in Distributed Quantum Computation

  2019cites this paper
• Potential Game Theoretic Learning for the Minimal Weighted Vertex Cover in Distributed Networking Systems

  2019cites this paper
• Parameterized Analysis of Multiobjective Evolutionary Algorithms and the Weighted Vertex Cover Problem

  2019cites this paper
• Parameterized Complexity Analysis of Randomized Search Heuristics

  2019cites this paper
• Multi-objective evolutionary computation for topology coverage assessment problem

  2019cites this paper
• A Game Theoretic Solver for the Minimum Weighted Vertex Cover

  2019cites this paper
• Theoretical Foundations of Immune-Inspired Randomized Search Heuristics for Optimization

  2019cites this paper
• The Runtime of the Compact Genetic Algorithm on Jump Functions

  2019cites this paper
• Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments

  2018cites this paper
• Performance Analysis of Evolutionary Optimization for the Bank Account Location Problem

  2018cites this paper
• A comparative performance analysis of evolutionary algorithms on k -median and facility location problems

  2018cites this paper
• Running-time analysis of evolutionary programming based on Lebesgue measure of searching space

  2018cites this paper
• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics

  2018cites this paper
• Better runtime guarantees via stochastic domination (hot-off-the-press track at GECCO 2018)

  2018cites this paper
• Theory for non-theoreticians: tutorial

  2018cites this paper
• Improving the run time of the (1 + 1) evolutionary algorithm with luby sequences

  2018cites this paper
• A comparative performance analysis of evolutionary algorithms on $${\varvec{k}}$$k-median and facility location problems

  2018cites this paper
• Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations

  2018cites this paper
• Performance Analysis of Evolutionary Algorithms for Steiner Tree Problems

  2017cites this paper
• Parameterised complexity analysis of evolutionary algorithms for combinatorial optimization problems

  2017cites this paper
• On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms

  2017cites this paper
• Improved runtime analysis of RLS and (1+1) EA for the dynamic vertex cover problem

  2017cites this paper
• Uncertain programming model for uncertain minimum weight vertex covering problem

  2017cites this paper
• Success rates analysis of three hybrid algorithms on SAT instances

  2017cites this paper
• A Multiobjective Cooperative Coevolutionary Algorithm for Hyperspectral Sparse Unmixing

  2017cites this paper
• Theory for Non-Theoreticians

  2016cites this paper
• Evolutionary Computation in Combinatorial Optimization

  2016influential citation
• First hitting time analysis of continuous evolutionary algorithms based on average gain

  2016cites this paper
• An Analytic Expression of Performance Rate , Fitness Value and Average Convergence Rate for a Class of Evolutionary Algorithms

  2016cites this paper
• Parameterized Analysis of Multiobjective Evolutionary Algorithms and the Weighted Vertex Cover Problem

  2016cites this paper
• Diversity optimization and parameterized analysis of heuristic search methods for combinatorial optimization problems

  2016cites this paper
• Maintaining 2-Approximations for the Dynamic Vertex Cover Problem Using Evolutionary Algorithms

  2015cites this paper
• Parameterized analysis of bio-inspired computation and the traveling salesperson problem.

  2015cites this paper
• Gray-Box Optimization using the Parameter-less Population Pyramid

  2015cites this paper
• An analytic expression of relative approximation error for a class of evolutionary algorithms

  2015cites this paper
• Grammatical evolution + multi-cores = automatic parallel programming!

  2015cites this paper
• An Analytic Expression of Performance Rate, Fitness Value and Average Convergence Rate for a Class of Evolutionary Algorithms

  2015cites this paper
• An Analytical Framework for Runtime of a Class of Continuous Evolutionary Algorithms

  2015cites this paper
• Link Approximation Performance Ratio and Average Convergence Rate

  2015cites this paper
• Parallel Evolutionary Algorithms

  2015cites this paper
• Analysis of Solution Quality of a Multiobjective Optimization-Based Evolutionary Algorithm for Knapsack Problem

  2015cites this paper
• Online test paper generation for a web-based mathematics testing environment

  2014cites this paper
• Fitness Landscape Analysis for Metaheuristic Performance Prediction

  2014cites this paper
• An evolutionary game optimization to vertex cover of dynamic networks

  2014cites this paper
• Performance Analysis of Evolutionary Algorithms for the Minimum Label Spanning Tree Problem

  2014cites this paper
• An evolutionary game optimization to vertex cover of dynamic networks

  2014cites this paper
• Uncertain programming model for uncertain minimum weight vertex covering problem

  2014cites this paper
• Runtime analysis for continuous (1+1) evolutionary algorithm based on average gain model

  2014cites this paper
• Parallel Evolutionary Algorithms Chapter in the Handbook of Computational Intelligence

  2013cites this paper
• Approximating vertex cover using edge-based representations

  2013cites this paper
• Towards a Snowdrift Game Optimization to Vertex Cover of Networks

  2013cites this paper
• Population Scalability Analysis of Abstract Population-based Random Search: Spectral Radius

  2012cites this paper
• A Novel Analysis of Super Linear Speedup for Population-based Evolutionary Algorithms

  2012cites this paper
• The use of tail inequalities on the probable computational time of randomized search heuristics

  2012cites this paper
• Evolutionary Optimization: Pitfalls and Booby Traps

  2012cites this paper
• A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem

  2012cites this paper
• Diversity Guided Evolutionary Programming: A novel approach for continuous optimization

  2012cites this paper
• Unpacking and Understanding Evolutionary Algorithms

  2012cites this paper
• Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

  2012cites this paper
• A large population size can be unhelpful in evolutionary algorithms

  2012cites this paper
• Superior-in-Status Analysis of Improved Genetic Algorithm for GTSP

  2012cites this paper
• Recurring Two-Stage Evolutionary Programming: A Novel Approach for Numeric Optimization

  2011cites this paper
• On the Analysis of the Immune-Inspired B-Cell Algorithm for the Vertex Cover Problem

  2011influential citation
• Novel Analysis of Population Scalability in Evolutionary Algorithms

  2011cites this paper
• On the effectiveness of crossover for migration in parallel evolutionary algorithms

  2011cites this paper
• Runtime Analysis of (1+1) Evolutionary Algorithm for a TSP Instance

  2010cites this paper
• On the approximation ability of evolutionary optimization with application to minimum set cover

  2010cites this paper
• Evolutionary Algorithms as Guaranteed Approximation Optimizers

  2010cites this paper
• On the performance of Recurring Multistage Evolutionary Algorithm for continuous function optimization

  2010cites this paper
• Bioinspired computation in combinatorial optimization: algorithms and their computational complexity

  2010cites this paper
• Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem

  2009cites this paper