About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Random Structures and Algorithms
Paper
Constructive bounds and exact expectations for the random assignment problem
Abstract
The random assignment problem is to choose a minimum-cost perfect matching in a complete n × n bipartite graph, whose edge weights are chosen randomly from some distribution such as the exponential distribution with mean 1. In this case it is known that the expectation does not grow unboundedly with n, but approaches some limiting value c* between 1.51 and 2. The limit is conjectured to be π2/6, while a recent conjecture is that for finite n, the expected cost is ∑ni=11/i2. This paper contains two principal results. First, by defining and analyzing a constructive algorithm, we show that the limiting expectation is c* < 1.94. Second, we extend the finite-n conjecture to partial assignments on complete m × n bipartite graphs and prove it in some limited cases. © 1999 John Wiley & Sons, Inc.