Data di Pubblicazione:
2018
Citazione:
Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension / S. Caracciolo, A. Di Gioacchino, E.M. Malatesta. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - 2018:8(2018 Aug 10).
Abstract:
In this work we consider the problem of finding the minimum-weight loop cover
of an undirected graph. This combinatorial optimization problem is called
2-matching and can be seen as a relaxation of the traveling salesman problem
since one does not have the unique loop condition. We consider this problem
both on the complete bipartite and complete graph embedded in a one dimensional
interval, the weights being chosen as a convex function of the Euclidean
distance between each couple of points. Randomness is introduced throwing
independently and uniformly the points in space. We derive the average optimal
cost in the limit of large number of points. We prove that the possible
solutions are characterized by the presence of "shoelace" loops containing 2 or
3 points of each type in the complete bipartite case, and 3, 4 or 5 points in
the complete one. This gives rise to an exponential number of possible
solutions scaling as p^N , where p is the plastic constant. This is at variance
to what happens in the previously studied one-dimensional models such as the
matching and the traveling salesman problem, where for every instance of the
disorder there is only one possible solution.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Physics - Disordered Systems and Neural Networks; Physics - Disordered Systems and Neural Networks
Elenco autori:
S. Caracciolo, A. Di Gioacchino, E.M. Malatesta
Link alla scheda completa: