00:00:00 / 00:00:00

Appears in collection : French Japanese Conference on Probability and Interactions

Combinatorial optimization problems are ubiquitous in various fields of practical and theoretical interest. The famous traveling salesman problem is one of them. One approach to tackle those problems is to use an Ising model whose Hamiltonian $H$ takes its minimum at a spin configuration, called a ground state, which corresponds to an optimal solution to the corresponding original problem. Standard MCMC methods, such as the Glauber dynamics and the Metropolis algorithm, have been used for decades to sample the Gibbs distribution, which is proportional to $e^{-H/T}$, hence close to the uniform distribution over the ground states when the temperature $T$ is very small. However, those MCMC methods are based on single-spin flip rules, hence prone to being slow. In this talk, I will explain three other MCMC methods, two among which are based on multi-spin flip rules, hence potentially fast. I will show several mathematical results, as well as numerical results to compare which is better in which context. This talk is based on joint work with Bruno Hideki Fukushima-Kimura and many others involved in the CREST project for the past five years.

Information about the video

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow


  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
  • Get notification updates
    for your favorite subjects
Give feedback
Loading the web debug toolbar…
Attempt #