THE RANDOM LINEAR BOTTLENECK ASSIGNMENT PROBLEM

Authors
PFERSCHY U
Citation
U. Pferschy, THE RANDOM LINEAR BOTTLENECK ASSIGNMENT PROBLEM, RAIRO. Recherche operationnelle, 30(2), 1996, pp. 127-142
Citations number
18
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
RAIRO. Recherche operationnelle → ACNP
ISSN journal
03990559
Volume
30
Issue
2
Year of publication
1996
Pages
127 - 142
Database
ISI
SICI code
0399-0559(1996)30:2<127:TRLBAP>2.0.ZU;2-W
Abstract
It is shown that the expected value of the optimal solution of an n x n linear bottleneck assignment problem with independently and identica lly distributed costs tends towards the infimum of the cost range as n tends to infinity. For fixed n and the uniform distribution explicit upper and lower bounds are given. Moreover; an algorithm with O (n(2)) expected running time is presented.