Time Complexity of Maximum Matching by Simulated Annealing

摘要

The random, heuristic search algorithm called simulated annealing is considered for the problem of finding the maximum cardinality matching in a graph. It is shown that neither a basic form of the algorithm, nor any other algorithm in a fairly large related class of algorithms, can find maximum cardinality matchings such that the average time required grows as a polynomial in the number of nodes of the graph. In contrast, it also shown for arbitrary graphs that a degenerate form of the basic annealing algorithm (obtained by letting temperature be a suitably chosen constant) produces matchings with nearly maximum cardinality in polynomial average time. Keywords: Algorithms, Performance, Theory, Verification, Maximum matching, Simulated annealing, Reprints. (MJM)