Maximum cardinality matchings on trees by randomized local search
Oliver Giel, Ingo Wegener · 2006
To understand the working principles of randomized search heuristics like evolutionary algorithms they are analyzed on optimization problems whose structure is well-studied. The idea is to investigate when it is possible to simulate clever optimization techniques for combinatorial optimization problems by random search. The maximum matching problem is well suited for this approach since long augmenting paths do not allow immediate improvements by local changes. It is known that randomized search heuristics like simulated annealing, the Metropolis algorithm, the (1+1) EA and randomized local search efficiently approximate maximum matchings for any graph; however, there are graphs where they fail to find maximum matchings in polynomial time. In this paper, we examine randomized local search (RLS) for graphs whose structure is simple. We show that RLS finds maximum matchings on trees in expected polynomial time.