Maximum Matching on Boltzmann Machines

Research output: Journal PublicationsJournal Article (refereed)peer-review

1 Citation (Scopus)


The Boltzmann machine is one of widely used neural network models used to cope with difficult combinatorial optimisation problems. It has been used to find near optimum solutions to such hard problems as graph partitioning and the Travelling Salesman problem. However, very little is known about the time complexity of solving combinatorial optimisation problems on Boltzmann machines. This issue is important because it will help us better understand the power of Boltzmann machines in dealing with hard problems. This paper studies the time complexity of maximum matching in a graph on Boltzmann machines. It is shown that some widely-used Boltzmann machines cannot find a maximum matching in average time polynomial in the number of nodes of the graph although there are conventional deterministic algorithms which solve the problem in polynomial time. On the other hand, this paper also shows that a simpler model of Boltzmann machines, with the 'temperature' parameter fixed at some constant, can find a near maximum matching in polynomial average time.
Original languageEnglish
Pages (from-to)49-53
Number of pages5
JournalNeural Processing Letters
Issue number1
Publication statusPublished - 1998
Externally publishedYes


  • Boltzmann Machine
  • Combinatorial Optimisation
  • Computational Complexity
  • Maximum Matching
  • Simulated Annealing


Dive into the research topics of 'Maximum Matching on Boltzmann Machines'. Together they form a unique fingerprint.

Cite this