A Generalization of the Random Assignment Problem

Details A Generalization of the Random Assignment Problem A Generalization of the Random Assignment Problem

2000-06-20

arxiv.org/abs/math/0006146v1

Mathematics

Combinatorics

40 pages, 3 figures

Scientific paper

We give a conjecture for the expected value of the optimal k-assignment in an m x n-matrix, where the entries are all exp(1)-distributed random variables or zeros. We prove this conjecture in the case there is a zero-cost $k-1$-assignment. Assuming our conjecture, we determine some limits, as $k=m=n\to \infty$, of the expected cost of an optimal n -assignment in an n x n-matrix with zeros in some region. If we take the region outside a quarter-circle inscribed in the square matrix, this limit is thus conjectured to be $\pi^2/24$. We give a computer-generated verification of a conjecture of Parisi for k=m=n=7 and of a conjecture of Coppersmith and Sorkin for $k\leq 5$. We have used the same computer program to verify this conjecture also for k=6.

Affiliated with

Also associated with

No associations

Rating

A Generalization of the Random Assignment Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Generalization of the Random Assignment Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Generalization of the Random Assignment Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-160718