ASYMPTOTICS IN THE RANDOM ASSIGNMENT PROBLEM

被引:83
作者
ALDOUS, D
机构
[1] Department of Statistics, University of California, Berkeley, 94720, CA
关键词
D O I
10.1007/BF01192719
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
We show that, in the usual probabilistic model for the random assignment problem, the optimal cost tends to a limit constant in probability and in expectation. The method involves construction of an infinite limit structure, in terms of which the limit constant is defined. But we cannot improve on the known numerical bounds for the limit.
引用
收藏
页码:507 / 534
页数:28
相关论文
共 13 条
[1]   ASYMPTOTICS FOR EUCLIDEAN MINIMAL SPANNING-TREES ON RANDOM POINTS [J].
ALDOUS, D ;
STEELE, JM .
PROBABILITY THEORY AND RELATED FIELDS, 1992, 92 (02) :247-258
[2]  
Aldous D.J., 1990, RANDOM STRUCT ALGOR, V1, P383
[3]  
ALDOUS DJ, 1992, 1990 P DURH S STOCH
[4]   ON LINEAR-PROGRAMS WITH RANDOM COSTS [J].
DYER, ME ;
FRIEZE, AM ;
MCDIARMID, CJH .
MATHEMATICAL PROGRAMMING, 1986, 35 (01) :3-16
[5]  
GOEMANS MX, 1989, LOWER BOUND EXPECTED
[6]   THE GROWTH AND COMPOSITION OF BRANCHING POPULATIONS [J].
JAGERS, P ;
NERMAN, O .
ADVANCES IN APPLIED PROBABILITY, 1984, 16 (02) :221-259
[7]  
KARP RM, 1987, DISCRETE ALGORITHMS, P1
[8]   ON THE SOLUTION OF THE RANDOM LINK MATCHING PROBLEMS [J].
MEZARD, M ;
PARISI, G .
JOURNAL DE PHYSIQUE, 1987, 48 (09) :1451-1459
[9]   THE STABLE DOUBLY INFINITE PEDIGREE PROCESS OF SUPERCRITICAL BRANCHING POPULATIONS [J].
NERMAN, O ;
JAGERS, P .
ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1984, 65 (03) :445-460
[10]   MARTINGALE INEQUALITIES, INTERPOLATION AND NP-COMPLETE PROBLEMS [J].
RHEE, WT ;
TALAGRAND, M .
MATHEMATICS OF OPERATIONS RESEARCH, 1989, 14 (01) :91-96