CS 789 THEORY SEMINAR [home]

Speaker: Balaji Prabhakar
Affiliation: Stanford University
Date: Monday, October 20, 2003
Title: The Parisi and Coppersmith-Sorkin Conjectures for the Random Assignment Problem

Abstract:

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. These conjectures have been open for some time now. This talk outlines the resolution of these conjectures. As background, we shall survey approaches to the assignment problem from computer science, statistical physics, and probability.

Joint work with Chandra Nair and Mayank Sharma.