  In this thesis I discuss combinatorial optimization problems, from the
statistical physics perspective. The starting point are the motivations which
brought physicists together with computer scientists and mathematicians to work
on this beautiful and deep topic. I give some elements of complexity theory,
and I motivate why the point of view of statistical physics leads to many
interesting results, as well as new questions. I discuss the connection between
combinatorial optimization problems and spin glasses. Finally, I briefly review
some topics of large deviation theory, as a way to go beyond average
quantities. As a concrete example of this, I show how the replica method can be
used to explore the large deviations of a well-known toy model of spin glasses,
the p-spin spherical model. In the second chapter I specialize in Euclidean
combinatorial optimization problems. In particular, I explain why these
problems, when embedded in a finite dimensional Euclidean space, are difficult
to deal with. I analyze several specific problems in one dimension to explain a
quite general technique to deal with one dimensional Euclidean combinatorial
optimization problems. Whenever possible, and in a detailed way for the
traveling-salesman-problem case, I also discuss how to proceed in two (and also
more) dimensions. In the last chapter I outline a promising approach to tackle
hard combinatorial optimization problems: quantum computing. After giving a
quick overview of the paradigm of quantum computation, I discuss in detail the
application of the so-called quantum annealing algorithm to a specific case of
the matching problem, also by providing a comparison between the performance of
a recent quantum annealer machine and a classical super-computer equipped with
an heuristic algorithm. Finally, I draw the conclusions of my work and I
suggest some interesting directions for future studies.
