Article ID: | iaor19881130 |
Country: | United States |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 387 |
End Page Number: | 403 |
Publication Date: | Apr 1988 |
Journal: | Journal of the Association for Computing Machinery |
Authors: | Sasaki Galen H., Hajek Bruce |
Keywords: | networks |
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 is 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