An assignment problem at high temperature
type: Item
instance of: scholarly article
title: An assignment problem at high temperature
zbMATH Open document ID: 1035.82015
author: Michel Talagrand
published in: The Annals of Probability
publication date: 2003-01-01T00:00:00Z
review text: The aim of this paper is to prove rigorously some physicists predictions on the so called stochastic assignment problem: given an independent sequence of \(N^2\) i.i.d. (uniform in \([0,1]\)) positive numbers \((a_{i,j})_{i,j \leq N}\), one wants to find \(\min_\sigma \sum_{i \leq N} a_{i,\sigma(i)}\) where the minimum runs over all the permutations \(\sigma\) of \(\{1, \dots, N\}\). Originally, the numbers \(a_{i,j}\) is the cost of assigning a job \(j\) to a worker \(i\). Introducing a Hamiltonian \(H_N(\sigma)=N \sum_{i \leq N} a_{i,\sigma(i)} \) and an inverse temperature \(\lambda\), physicists used ideas from statistical mechanics and spin-glasses theory to predict its behavior. They have in particular predicted that this minimal cost is asymptotically \(\pi^2/6\), and this result has been recently proved by Aldous. This asymptotic behavior is not the only interesting feature of this model and, like in many other spin-glass models, another physicists prediction is that this model is in a high temperature phase for all values of \(\lambda\), i.e. the so called replica-symmetry solution holds and the random variables are in some sense nearly independent under the Gibbs measure defined by the above Hamiltonian. This problem is very difficult to prove rigorously and in similar problems a first step is to prove a ``very high temperature regime'', i.e. that it is true for temperature less than a given \(\lambda_0\). According to the author, this is also very difficult to prove, but he managed to prove a weaker result for a modified model presenting the same features as the original one; in the new model, the Hamiltonian is given for integers \(M,N\) by \(H_{M,N}(\sigma)=N \sum_{i \leq N} a_{i,\sigma(i)}\) where the configuration is now a map \(\sigma\) from \(\{1, \dots, N\}\) to \(\{1 \dots M\}\), with \(N,M\) goes to infinity with a fixed ratio (\(M=[(1+\alpha N)]\), with \(\alpha >0\)). This model appears to be easier and in this case the author proves the very h…
reviewed by: Arnaud Le Ny
Mathematics Subject Classification ID: 82B23
Mathematics Subject Classification ID: 82B44
zbMATH DE Number: 1933032
zbMATH Keywords: spin glasses
zbMATH Keywords: replica symmetry
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1048516537
OpenAlex ID: W2063112645
cites work: Asymptotics in the random assignment problem
cites work: The \(\zeta(2)\) limit in the random assignment problem
cites work: The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
cites work: Huge random structures and mean field models for spin glasses
DOI: 10.1214/AOP/1048516537
description: scientific article; zbMATH DE number 1933032