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

### Fingerprint

### ASJC Scopus subject areas

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

### Cite this

*Journal of the ACM (JACM)*,

*35*(2), 387-403. https://doi.org/10.1145/42282.46160

**The time complexity of maximum matching by simulated annealing.** / Sasaki, Galen H.; Hajek, Bruce.

Research output: Contribution to journal › Article

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

}

TY - JOUR

T1 - The time complexity of maximum matching by simulated annealing

AU - Sasaki, Galen H.

AU - Hajek, Bruce

PY - 1988/4/1

Y1 - 1988/4/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0023999795&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023999795&partnerID=8YFLogxK

U2 - 10.1145/42282.46160

DO - 10.1145/42282.46160

M3 - Article

AN - SCOPUS:0023999795

VL - 35

SP - 387

EP - 403

JO - Journal of the ACM

JF - Journal of the ACM

SN - 0004-5411

IS - 2

ER -