Suppose that there are n jobs and n machines and it costs c(i,j)
to execute job i on machine j. The assignment problem concerns the
determination of a one-to-one assignment of jobs onto machines so
as to minimize the cost of executing all the jobs. When the c(i,j)
are independent and identically distributed exponentials of mean 1,
Parisi has made the beautiful conjecture that the average minimum
cost equals the sum of 1/i^2 from i=1 to n.

Coppersmith and Sorkin have generalized Parisi's conjecture to the
average value of the smallest k-assignment when there are n jobs
and m machines.

This talk outlines the resolution of these conjectures. As background,
we shall survey approaches to the assignment problem from combinatorial
optimization, statistical physics, and probability.

Joint work with Chandra Nair and Mayank Sharma.