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

Fingerprint

Simulated annealing
Polynomials
Annealing
Temperature

ASJC Scopus subject areas

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

Cite this

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

In: Journal of the ACM (JACM), Vol. 35, No. 2, 01.04.1988, p. 387-403.

Research output: Contribution to journalArticle

@article{7c3905cb973b4dcb9759033f8e11dba9,
title = "The time complexity of maximum matching by simulated annealing",
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.",
author = "Sasaki, {Galen H.} and Bruce Hajek",
year = "1988",
month = "4",
day = "1",
doi = "10.1145/42282.46160",
language = "English (US)",
volume = "35",
pages = "387--403",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

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 -