Problema de la asignación estocástica

Question

Dado un $n \times n$ real de la matriz $C$, podemos intentar maximizar $$\Phi(C, \pi) = \frac{1}{n} \sum_{i} C_{i,\pi(i)} $$ más de $\pi \in S_n$, el conjunto de todas las permutaciones en $n$ objetos. ¿Qué se puede decir acerca de este problema si el $C_{ij}$ son variables aleatorias? Evidencia numérica indica que para una distribución normal, independientes de las entradas de $C_{ij} \sim N(0,1)$, el valor óptimo $argmax_\pi \Phi$ de la función objetivo tiene un promedio de alrededor de $.67 (\log n)^.82$ y una desviación estándar de aproximadamente igual a $.84/\sqrt{n \log n}$ si $n \ge 10$ o así.

Es esto conocido? Hay una teoría que implica estas observaciones y las hace más precisas?

Answer 1

Usted se está preguntando sobre el valor óptimo de la asignación al azar problema, que ha recibido un buen montón de estudio en el último par de décadas. La mayor parte del trabajo ha sido con el uniforme de$[0,1]$ o exponencial$(1)$ variables aleatorias, sin embargo, y con los mínimos. Tal vez sea porque el uniforme y exponencial de los casos han resultado más fáciles de analizar. Aunque no creo que ha habido mucho trabajo explícito en el caso en que los costos se $N(0,1)$, podemos componer algunos de los resultados a decir que el valor esperado que estás buscando es $$E[\Phi_n] \sim A \sqrt{\log n},$$ for some constant $$.

Definir $$L_n = \min_{\pi \in S_n} \sum_i C_{i,\pi(i)}.$$ Frenk, van Houweninge, and Rinnooy Kan ("Order statistics and the linear assignment problem," Computing 39 (2), 165-174, 1987) proved that under some mild conditions on the cumulative distribution function $F$ that, for some constant $C$ that depends on $F$, $$E[L_n] \sim C n F^{-1}(1/n).$$ Since the normal pdf is symmetric we can apply asymptotic estimates for $F^{-1}(1-1/n)$ (i.e., the maximum rather than the minimum) so that when costs are $N(0,1)$, for some constant $Un$, $$E[\Phi_n] \sim A \sqrt{\log n},$$ que no está lejos de lo que su evidencia numérica dice. (Si $C$ resulta ser $1$ en el caso normal, entonces tendríamos $A = \sqrt{2}$.)

---

Para la exponencial$(1)$ distribución, Aldous (" $\zeta(2)$ en el límite de la asignación al azar problema," al Azar Algoritmos y Estructuras de 18 (4), 381-418, 2001), demostró que $$\lim_{n \to \infty} E[L_n] = \zeta(2) = \frac{\pi^2}{6}.$$ Aldous notes that his result holds for distributions with the same density at $0$ (assuming this exists and is positive), so we have the same limiting value if costs are uniform$[0,1]$. This was followed a few years later by independent work from Linusson and Wästlund ("A proof of Parisi's conjecture on the random assignment problem," Probability Theory and Related Fields 128 (3), 419-400, 2004) and Nair, Prabhakar, and Sharma ("Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures," Random Structures and Algorithms 27 (4), 413-444, 2005) proving that in the exponential$(1)$ case $$E[L_n] = \sum_{i=1}^n \frac{1}{i^2}.$$

---

Para más información, véase la reciente encuesta de papel por Krokhmal y Pardalos ("asignación al Azar de los problemas," European Journal of Operational Research 194, 1-17, 2009). Hay algunos resultados que allí se indican en las varianzas. Por ejemplo, en la exponencial$(1)$ de los casos, parece que $$\sigma^2(L_n) = \frac{4\zeta(2) - 4\zeta(3)}{n} + O(n^{-2}).$$