In this paper we introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. We will focus on the maximum clique problem and we will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising. Our effort in this paper is to be clear as well to those readers who are not in the field.

Iovanella, A., Scoppola, B., Scoppola, E. (2007). Some spin glass ideas applied to the clique problem. In Journal of Statistical Physics (pp.895-915). NEW YORK : SPRINGER/PLENUM PUBLISHERS [10.1007/s10955-006-9255-z].

Some spin glass ideas applied to the clique problem

IOVANELLA, ANTONIO;SCOPPOLA, BENEDETTO;
2007-01-01

Abstract

In this paper we introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. We will focus on the maximum clique problem and we will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising. Our effort in this paper is to be clear as well to those readers who are not in the field.
Conference on Mathematical Physics of Spin Glasses
Cortona, ITALY
2005
Rilevanza internazionale
2007
Settore MAT/07 - FISICA MATEMATICA
English
Clique problem; Markov Chain Monte Carlo
http://hdl.handle.net/2108/56448
Intervento a convegno
Iovanella, A., Scoppola, B., Scoppola, E. (2007). Some spin glass ideas applied to the clique problem. In Journal of Statistical Physics (pp.895-915). NEW YORK : SPRINGER/PLENUM PUBLISHERS [10.1007/s10955-006-9255-z].
Iovanella, A; Scoppola, B; Scoppola, E
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/35147
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 10
social impact