We consider models of assignment for random N blue points and N red points on an interval of length 2N, in which the cost for connecting a blue point in x to a red point in y  is the concave function |x - y |p , for 0 < p  < 1. Contrarily to the convex case p  > 1, where the optimal matching is trivially determined, here the optimization is non-trivial. The purpose of this paper is to introduce a special configuration, that we call the Dyck matching, and to study its statistical properties. We compute exactly the average cost, in the asymptotic limit of large N, together with the first subleading correction. The scaling is remarkable: it is of order N for p ≤ 1/2, order N In N for p = 1/2, and N1/2+p for p ≤ 1/2, and it is universal for a wide class of models. We conjecture that the average cost of the Dyck matching has the same scaling in N as the cost of the optimal matching, and we produce numerical data in support of this conjecture. We hope to produce a proof of this claim in future work.

The Dyck bound in the concave 1-dimensional random assignment model / S. Caracciolo, M.P. D'Achille, V. Erba, A. Sportiello. - In: JOURNAL OF PHYSICS. A, MATHEMATICAL AND THEORETICAL. - ISSN 1751-8113. - 53:6(2020), pp. 064001.1-064001.26. [10.1088/1751-8121/ab4a34]

The Dyck bound in the concave 1-dimensional random assignment model

Caracciolo S.;Erba V.;
2020

Abstract

We consider models of assignment for random N blue points and N red points on an interval of length 2N, in which the cost for connecting a blue point in x to a red point in y  is the concave function |x - y |p , for 0 < p  < 1. Contrarily to the convex case p  > 1, where the optimal matching is trivially determined, here the optimization is non-trivial. The purpose of this paper is to introduce a special configuration, that we call the Dyck matching, and to study its statistical properties. We compute exactly the average cost, in the asymptotic limit of large N, together with the first subleading correction. The scaling is remarkable: it is of order N for p ≤ 1/2, order N In N for p = 1/2, and N1/2+p for p ≤ 1/2, and it is universal for a wide class of models. We conjecture that the average cost of the Dyck matching has the same scaling in N as the cost of the optimal matching, and we produce numerical data in support of this conjecture. We hope to produce a proof of this claim in future work.
assignment problem; disordered systems; Dyck paths; Physics - Disordered Systems and Neural Networks; Physics - Disordered Systems and Neural Networks
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
JOURNAL OF PHYSICS. A, MATHEMATICAL AND THEORETICAL
Article (author)
File in questo prodotto:
File Dimensione Formato  
draft.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 454.87 kB
Formato Adobe PDF
454.87 kB Adobe PDF Visualizza/Apri
Caracciolo_2020_J._Phys._A _Math._Theor._53_064001.pdf

non disponibili

Tipologia: Publisher's version/PDF
Dimensione 1.8 MB
Formato Adobe PDF
1.8 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/727565
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact