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.

RANDOM COMBINATORIAL OPTIMIZATION PROBLEMS: MEAN FIELD AND FINITE-DIMENSIONAL RESULTS / E.m. Malatesta ; coordinator: F. RAGUSA ; advisors: S. CARACCIOLO, G. PARISI. - : . DIPARTIMENTO DI FISICA, 2018 Dec 21. ((31. ciclo, Anno Accademico 2018. [10.13130/malatesta-enrico-maria_phd2018-12-21].

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

E.M. Malatesta
2018-12-21

Abstract

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.
CARACCIOLO, SERGIO
RAGUSA, FRANCESCO
Disordered Systems, Combinatorial Optimization, Matching and Traveling Salesman Problem, Replica Method
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
RANDOM COMBINATORIAL OPTIMIZATION PROBLEMS: MEAN FIELD AND FINITE-DIMENSIONAL RESULTS / E.m. Malatesta ; coordinator: F. RAGUSA ; advisors: S. CARACCIOLO, G. PARISI. - : . DIPARTIMENTO DI FISICA, 2018 Dec 21. ((31. ciclo, Anno Accademico 2018. [10.13130/malatesta-enrico-maria_phd2018-12-21].
Doctoral Thesis
File in questo prodotto:
File Dimensione Formato  
phd_unimi_R11443.pdf

accesso aperto

Tipologia: Tesi di dottorato completa
Dimensione 2.8 MB
Formato Adobe PDF
2.8 MB Adobe PDF Visualizza/Apri
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/605056
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact