Adaptive mean field approximation algorithm with critical temperature for combinatorial optimization problem

The mean field approximation algorithm has applied by many researchers to solve combinatorial optimization problems since 1980’s. It is well known that critical phenomena occur in the course of annealing of the mean field approximation algorithm, and the determination of critical temperature has been studied. In spite of an essential importance of the critical temperature to annealing schedule there is no research on algorithm with considering the critical temperature. This paper presents an adaptive mean field approximation algorithm with ‘adaptive annealing’ in which annealing schedule is modified by estimation of the critical temperature. In experiments of maximum clique and graph partition problems, in comparison with other algorithms, the authors get better results and speed-up effect by adaptive mean field approximation algorithm. [In Japanese.]