Coincidencia de costo mínimo para un gráfico bipartito completo al azar

Question

Editado

Tengo este problema, cuando la lectura de Goeman de notas de la conferencia http://www-math.mit.edu/~goemans/18433S11/juego-notas.pdf

Problema: Ejercicio 1-16. ...Un completo bipartito grafo con n vértices en cada lado de la desdoblamiento, y supongamos que todos los $c_{ij}$ (para i, j $\in$ {1, · · · , n}) son todos independientes uniforme de variables al azar entre 0 y 1. Tomar 5 diferentes valores de n (siendo el más importante el de unos pocos cientos) y para cada uno de calcular el costo mínimo de asignación de valor para los 5 casos. Cualquier conjetura sobre cómo este valor aumenta a medida que n tiende a infinito. Cualquier conjetura sobre cómo este valor aumenta a medida que n tiende a infinito. ¿No le parece converger? A qué valor? Sorprendido? (Sí, debe ser, y es normal que no entiende por qué).

Pregunta: Alguien sabe donde el costo mínimo se convergen, y la razón?

Answer 1

Empíricamente mediante R

require(clue)
n <- 200 
m <- matrix(runif(n^2), ncol=n) 
s <- solve_LSAP(m) 
sum(m[cbind(seq_along(s), s)])

produce resultados de alrededor de 1.6.

Poniendo David J. Aldous, El zeta(2) en el límite de la asignación al azar problema [nota por Srivatsan] y el comentario en la conjetura de 4 de No Calderero y Gregory B. Sorkin, Constructivo, de los límites y exacta de las expectativas para la asignación al azar problema [donde esto es una conjetura 3] el resultado es $\pi^2/6 \approx 1.6449$. Tanto vale la pena leer.

Esto puede no ser una sorpresa dado que el costo más bajo del borde es probable que sea menos de $1/n^2$. En ther otro lado, no es difícil encontrar el límite mismo por las razones equivocadas.