Evolutionary Algorithms and the Maximum Matching Problem

Loading...
Thumbnail Image

Date

2003-12-23

Journal Title

Journal ISSN

Volume Title

Publisher

Universität Dortmund

Abstract

Randomized search heuristics like evolutionary algorithms are mostly applied to problems whose structure is not completely known but also to combinatorial optimization problems. Practitioners report surprising successes but almost no results with theoretically well-founded analyses exist. Such an analysis is started in this paper for a fundamental evolutionary algorithm and the well-known maximum matching problem. It is proven that the evolutionary algorithm is a polynomial-time randomized approximation scheme (PRAS) for this optimization problem, although the algorithm does not employ the idea of augmenting paths. Moreover, for very simple graphs it is proved that the expected optimization time of the algorithm is polynomially bounded and bipartite graphs are constructed where this time grows exponentially.

Description

Table of contents

Keywords

Citation