Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs

Maria Chiara Angelini and Federico Ricci-Tersenghi
Phys. Rev. E 100, 013302 – Published 2 July 2019

Abstract

The effectiveness of stochastic algorithms based on Monte Carlo dynamics in solving hard optimization problems is mostly unknown. Beyond the basic statement that at a dynamical phase transition the ergodicity breaks and a Monte Carlo dynamics cannot sample correctly the probability distribution in times linear in the system size, there are almost no predictions or intuitions on the behavior of this class of stochastic dynamics. The situation is particularly intricate because, when using a Monte Carlo–based algorithm as an optimization algorithm, one is usually interested in the out-of-equilibrium behavior, which is very hard to analyze. Here we focus on the use of parallel tempering in the search for the largest independent set in a sparse random graph, showing that it can find solutions well beyond the dynamical threshold. Comparison with state-of-the-art message passing algorithms reveals that parallel tempering is definitely the algorithm performing best, although a theory explaining its behavior is still lacking.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 30 April 2019

DOI:https://doi.org/10.1103/PhysRevE.100.013302

©2019 American Physical Society

Physics Subject Headings (PhySH)

Statistical Physics & Thermodynamics

Authors & Affiliations

Maria Chiara Angelini1 and Federico Ricci-Tersenghi1,2

  • 1Dipartimento di Fisica, Università “La Sapienza,” Piazzale Aldo Moro 5, 00185 Rome, Italy
  • 2INFN, Sezione di Roma 1, and Rome Unit, CNR Nanotec, Piazzale Aldo Moro 5, 00185 Rome, Italy

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 100, Iss. 1 — July 2019

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×