Die ζ(2)-Grenze im Problem der zufälligen Zuordnung

Zusammenfassung Das Problem der zufälligen Zuordnung (oder bipartite Zuordnung) fragt nach A n =min π ∑ c ( i , π( i )), wobei ( c ( i , j )) eine n × n Matrix mit i.i.d. Einträgen ist, sagen wir mit einer Exponentialverteilung(1), und das Minimum über Permutationen π ist. Mézard und Parisi (1987) verwendeten die Replikamethode aus der statistischen Physik, um nicht rigoros zu argumentieren, dass EA n →ζ(2)=π 2 /6. Aldous (1992) identifizierte das Limit in Bezug auf ein Zuordnungsproblem auf einem limitinfinite Baum. Hier konstruieren wir die optimale Zuordnung auf dem unendlichen Baum. Dies liefert einen rigorosen Beweis der ζ(2)-Grenze und der vermuteten Grenzverteilung der Kantenkosten und ihrer Rangordnungen in der optimalen Zuordnung. Es ergibt auch die asymptotische essentielle Eindeutigkeitseigenschaft: Jede fast-optimale Zuordnung stimmt mit der optimalen Zuordnung überein, mit Ausnahme eines kleinen Anteils von Kanten. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001