Several optimization problems can be stated as disordered systems problems. This fact encouraged a fruitful exchange of knowledge and technical tools from one field to the other. The physical insight made possible to design new algorithms based on some physical ideas.The first part of this thesis is devoted to an introduction to the physics of disordered systems and cavity methods, with a specific attention to its relation with combinatorial optimization.The second part of the thesis is devoted to the description of some new results. In chapter 6 we give a general method to find bounds for the cost of the optimal configuration of an optimization problem. We apply it to the ground state of Ising Spin Glasses on Random Graphs.In chapter 7 we analyze the behaviour of an algorithm based on the passing of messages (Belief Propagation) on the Assignment Problem. This algorithm surprisingly results to be exact for the Assignment problem. We give a proof of the exactness of this algorithm and describe its behaviour.In chapter 8 we discuss some variants of the Assignment problem and introduce then a variant: the one-in-two problem, suggested us as a simpler but no easier version of the Traveling Salesman Problem.

Cavity methods in optimization problems : exact and approximated algorithms / D. Fichera ; S. Caracciolo, G. Bellini. - : . DIPARTIMENTO DI FISICA, 2008 Feb 20. ((20. ciclo, Anno Accademico 2006/2007.

Cavity methods in optimization problems : exact and approximated algorithms

D. Fichera
2008-02-20

Abstract

Several optimization problems can be stated as disordered systems problems. This fact encouraged a fruitful exchange of knowledge and technical tools from one field to the other. The physical insight made possible to design new algorithms based on some physical ideas.The first part of this thesis is devoted to an introduction to the physics of disordered systems and cavity methods, with a specific attention to its relation with combinatorial optimization.The second part of the thesis is devoted to the description of some new results. In chapter 6 we give a general method to find bounds for the cost of the optimal configuration of an optimization problem. We apply it to the ground state of Ising Spin Glasses on Random Graphs.In chapter 7 we analyze the behaviour of an algorithm based on the passing of messages (Belief Propagation) on the Assignment Problem. This algorithm surprisingly results to be exact for the Assignment problem. We give a proof of the exactness of this algorithm and describe its behaviour.In chapter 8 we discuss some variants of the Assignment problem and introduce then a variant: the one-in-two problem, suggested us as a simpler but no easier version of the Traveling Salesman Problem.
CARACCIOLO, SERGIO
BELLINI, GIANPAOLO
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
Cavity methods in optimization problems : exact and approximated algorithms / D. Fichera ; S. Caracciolo, G. Bellini. - : . DIPARTIMENTO DI FISICA, 2008 Feb 20. ((20. ciclo, Anno Accademico 2006/2007.
Doctoral Thesis
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/2434/58655
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact