RANDOM COMBINATORIAL OPTIMIZATION PROBLEMS: MEAN FIELD AND FINITE-DIMENSIONAL RESULTS

Until the introduction of the first spin glass model by Edwards and Anderson in 1975, the research area of disordered systems has undergone a huge progress, thanks to the introduction of new analytical techniques and numerical tools, as long as the development of novel concepts and ideas. In particular, the rich phenomenology found by the extensive study of mean field spin glass models, not only proved to be the basis for an explanation of many different physical phenomena and permitted to strengthen the traditional relationship between physics and mathematics, but also it allowed physicist to apply those concepts to research areas that were thought to be completely disconnected from physics before. In this thesis I will analyze combinatorial optimization problems, from a physics point of view. In the first two chapters I will review some basic notions of statistical physics of disordered systems, such as random graph theory, the mean-field approximation, spin glasses and combinatorial optimization. The replica method will also be introduced and applied to the Sherrington-Kirkpatrick model, one of the simplest mean-field models of spin-glasses. The second part of the thesis deals with mean-field combinatorial optimization problems. The attention will be focused on finite-size corrections of random integer matching problems (chapter 3) and fractional ones (chapter 4). In chapter 5 I will discuss a very general relation connecting multi-overlaps and the moments of the cavity magnetization distribution. In the third part the Euclidean counterparts of random optimization problems are considered. I will start solving the traveling-salesman-problem (TSP) in one dimension both in its bipartite and monopartite version (chapter 6). In chapter 7 I will discuss the possible optimal solutions of the 2-factor problem. In chapter 8 I will solve the bipartite TSP in two dimensions, in the limit of large number of points. Chapter 9 contain some conclusions.