A Generalization of the Random Assignment Problem
| dc.creator | Linusson, Svante | |
| dc.creator | Waestlund, Johan | |
| dc.date | 2000-06-20 | |
| dc.date.accessioned | 2026-07-07T04:35:58Z | |
| dc.date.available | 2026-07-07T04:35:58Z | |
| dc.description | 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 $π^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. | |
| dc.description | 40 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/math/0006146 | |
| dc.identifier | http://arxiv.org/abs/math/0006146 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/59441 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.title | A Generalization of the Random Assignment Problem | |
| dc.type | text |