Probability Study Group

This is an informal study group covering topics in probability. Speakers volunteer to present recent papers on topics selected by the group at large. Grad students, postdocs, and faculty are all encouraged to attend.

Details

The Minimum Cost of a Random Assignment

by Mustazee Rahman | University of Toronto
Time: 15:00  (Friday, Apr. 13, 2012)
Location: Fields Institute, 222 College St
Abstract:
Given two disjoint n element sets X and Y and cost functions c(x,y), the assignment or bipartite matching problem seeks a permutation f : X -> Y such that the cost $sum_{x \in X} c(x, f(x))$ is minimum. The randomized version of this consists of taking the costs c(x,y) to be independent and identically distributed random variables, for example, rate 1 exponentials. We will survey known results about the random assignment problem, and in particular, prove the surprising result that the expected minimum cost C(n) with exp(1) costs converges to the constant zeta(2) = 1 + 1/4 + 1/9 + .... The proof is purely combinatorial, following an argument of Linusson and Waslund.

Dates in this series

· Monday, Feb. 08, 2010: Liouville Property, Amenability, Discrete Fractals and Automaton Groups (Gidi Amir)
· Monday, Feb. 22, 2010: Scaling Exponents for Directed Polymers in 1+1 Dimensions, Part III (Tom Alberts)
· Monday, Mar. 01, 2010: Scaling exponents for directed polymers in dimension 1+1, part III (Tom Alberts)
· Monday, Apr. 26, 2010: More details of Jeff Schenker's proof of eigenvector localization for band matrices (Ben Rifkind)
· Monday, May. 10, 2010: The Doob h-transform: theory and examples (Alex Bloemendal)
· Monday, May. 17, 2010: Doob's h-transform: a few more examples (Alex Bloemendal)
· Monday, Oct. 04, 2010: Sample Path Properties of Stochastic Flows (Dima Dolgopyat)
· Monday, Oct. 18, 2010: Sample Path Properties of Stochastic Flows, Part II (Dima Dolgopyat)
· Monday, Oct. 25, 2010: Sample Path Properties of Stochastic Flows, Part III (Dima Dolgopyat)
· Friday, Jul. 29, 2011: SLE in multiply connected domains (Gregory F. Lawler)
· Friday, Dec. 02, 2011: A model of migration under constraints (Raoul Normand)
· Friday, Jan. 20, 2012: Local Limit Theorem for Random Walks on Free Groups (Andrew Stewart)
· Friday, Feb. 03, 2012: The Law of the Iterated Logarithm (Eric Hart)
· Friday, Mar. 16, 2012: Random matrices: Getting inside the bulk! (Van Vu)
· Friday, Mar. 30, 2012: A Brief Introduction to Compressed Sensing (Kai Yang)
· Friday, Apr. 13, 2012: The Minimum Cost of a Random Assignment (Mustazee Rahman)
· Tuesday, May. 01, 2012: An Introduction to the Dirichlet Process (Tom Alberts)