The time complexity of maximum matching by simulated annealing

Galen H. Sasaki, Bruce Hajek

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)387-403
Number of pages17
JournalJournal of the ACM (JACM)
Volume35
Issue number2
DOIs
StatePublished - 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