Evolutionary algorithms and the maximum matching problem

DOI10.1007/3-540-36494-3_37MaRDI QIDQ4418669zbMATH OpenFDO

Authors Oliver Giel, Ingo Wegener

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070415.htm, http://hdl.handle.net/2003/5432

Mathematics Subject Classification ID

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

Recommendations

• Evolutionary algorithms and matroid optimization problems
• The time complexity of maximum matching by simulated annealing
• Maximum matchings in general graphs through randomization
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• STACS 2004

Cited in

(39)

• Runtime analysis of a simple ant colony optimization algorithm
• Comparison of simple diversity mechanisms on plateau functions
• A comparative performance analysis of evolutionary algorithms on k-median and facility location problems
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• A relation-algebraic view on evolutionary algorithms for some graph problems
• Adaptive drift analysis
• Multiplicative drift analysis
• Black-box search by unbiased variation
• Fixed-parameter evolutionary algorithms and the vertex cover problem
• The runtime of the compact genetic algorithm on jump functions
• Algorithmic analysis of a basic evolutionary algorithm for continuous optimization
• Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
• How the (1+1) ES using isotropic mutations minimizes positive definite quadratic forms
• Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems
• SYMBIOTIC EVOLUTIONARY ALGORITHM, A REMEDY FOR LINKAGE PROBLEM
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• On the approximation ability of evolutionary optimization with application to minimum set cover
• The use of tail inequalities on the probable computational time of randomized search heuristics
• Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem
• Variable solution structure can be helpful in evolutionary optimization
• Win-win match using a genetic algorithm
• Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax
• Choosing the right algorithm with hints from complexity theory
• Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem
• Practical performance models of algorithms in evolutionary program induction and other domains
• Free lunches on the discrete Lipschitz class
• Runtime analysis of the 1-ANT ant colony optimizer
• Computing minimum cuts by randomized search heuristics
• Hybridizing evolutionary algorithms with variable-depth search to overcome local optima
• Simplified drift analysis for proving lower bounds in evolutionary computation
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Evolutionary algorithms and dynamic programming
• Fourier analysis meets runtime analysis: precise runtimes on plateaus
• Plateaus can be harder in multi-objective optimization
• Evolutionary algorithms and matroid optimization problems
• Minimum spanning trees made easier via multi-objective optimization
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Runtime analysis of a binary particle swarm optimizer

This page was built for publication: Evolutionary algorithms and the maximum matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4418669)