Probability and statisitics in the service of computer science: illustrations using the assignment problem

Recent work on the assignment problem is surveyed with the aim of illustrating the contribution that stochastic thinking can make to problems of interest to computer scientists. The assignment problem is thus examined in connection with the analysis of greedy algorithms, marriage lemmas, linear programming with random costs, randomization based matching, stochastic programming, and statistical mechanics. (The survey is based on the invited presentation given during the “Statistics Days at FSU” in March 1990.)