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.
|Titolo:||Cavity methods in optimization problems : exact and approximated algorithms|
|Supervisori e coordinatori interni:||BELLINI, GIANPAOLO|
|Data di pubblicazione:||20-feb-2008|
|Settore Scientifico Disciplinare:||Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici|
|Citazione:||Cavity methods in optimization problems : exact and approximated algorithms / D. Fichera ; S. Caracciolo, G. Bellini. - Milano : Università degli studi di Milano. DIPARTIMENTO DI FISICA, 2008 Feb 20. ((20. ciclo, Anno Accademico 2006/2007.|
|Appare nelle tipologie:||13 - Tesi di dottorato discussa entro ottobre 2010|