### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 387-403 |

Number of pages | 17 |

Journal | Journal of the ACM (JACM) |

Volume | 35 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1 1988 |

### ASJC Scopus subject areas

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

## Fingerprint Dive into the research topics of 'The time complexity of maximum matching by simulated annealing'. Together they form a unique fingerprint.

## Cite this

Sasaki, G. H., & Hajek, B. (1988). The time complexity of maximum matching by simulated annealing.

*Journal of the ACM (JACM)*,*35*(2), 387-403. https://doi.org/10.1145/42282.46160