Proofs of the Parisi and Coppersmith-Sorkin conjectures in the random assignment problem.

摘要

This thesis concerns the resolution of the Parisi's and Coppersmith-Sorkin Conjectures in the Random Assignment Problem. The assignment problem is an optimization problem of interest in a variety of scenarios. It comes up in assigning jobs to machines to minimize costs, in assigning packets from input line cards to output line cards to maximize throughput in internet routers, in assigning flights and crews to routes to maximize airline revenue; to name a few.; Of interest are both the optimal assignment and the optimal value. In a deterministic setting, a famous algorithm called the Hungarian method provides an efficient way of computing the optimal assignment. In a random environment, i.e. where the costs are modeled as random variables, one is often interested in the properties of the minimum cost assignment.; Based on some numerical evidence Parisi conjectured an expression for the expected value of the minimum cost under the case when the cost variables were independent and exponentially distributed. This conjecture was later extended by Coppersmith and Sorkin to a more general setting.; This thesis makes the following main contribution: It resolves both the Parisi and Coppersmith-Sorkin conjectures regarding the expected cost of the minimum assignment. Further, it completes an argument put forth by Dotsenko that aimed to solve Parisi's conjecture. This thesis also contains some results and conjectures towards the entire distribution of the minimum cost.