The time complexity of maximum matching by simulated annealing

The time complexity of maximum matching by simulated annealing

0.00 Avg rating0 Votes
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: ,
Keywords: networks
Abstract:

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 nearly maximum cardinality in polynomial average time.

Reviews

Required fields are marked *. Your email address will not be published.