A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem

Details A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem

2003-07-28

arxiv.org/abs/math/0307357v1

Mathematics

Combinatorics

19 pages

Scientific paper

We prove the main conjecture of the paper ``On the expected value of the minimum assignment'' by Marshall W. Buck, Clara S. Chan, and David P. Robbins (Random Structures & Algorithms 21 (2002), no. 1, 33--58). This is a vast generalization of a formula conjectured by Giorgio Parisi for the $n$ by $n$ random assignment problem. We combine the urn model from the article by Buck, Chan and Robbins, with our proof of Parisi's conjecture in our article posted on the Arxiv in March this year. Our new theorem generalize simultaneously our main theorem from that article and the conjecture by Buck, Chan and Robbins. Using the urn model we avoid several technical difficulties from our previous proof of Parisi's conjecture and get a shorter proof in a conceptually more appealling setting.

Affiliated with

Also associated with

No associations

Rating

A proof of a conjecture of Buck, Chan and Robbins on 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 proof of a conjecture of Buck, Chan and Robbins on the random assignment problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-108085