Name
Title | ||
|---|---|---|
On the expected optimal value of random assignment problems: experimental results and open questions |
Abstract | ||
|---|---|---|
In the paper, we study the expected optimal value of random linear assignment problems, whose data are random variables with the uniform and the exponential distributions. An interior point approach is used to solve large-scale dense assignment problems with size up to 10,000 nodes and 100 million edges. Our computational results indicate the validity of a long-standing conjecture about the limiting value of the expected optimal assignment. Some interesting open problems and extensions are discussed. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/BF01299451 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
Computational experimentation,linear assignment problem,random variables,interior point methods | Weapon target assignment problem,Mathematical optimization,Random variable,Quadratic assignment problem,Generalized assignment problem,Random assignment,Assignment problem,Multivariate random variable,Linear bottleneck assignment problem,Mathematics | Journal |
Volume | Issue | Citations |
2 | 3 | 6 |
PageRank | References | Authors |
0.91 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panos M. Pardalos | 1 | 698 | 98.99 |
| K. G. Ramakrishnan | 2 | 587 | 98.53 |