The random linear bottleneck assignment problem

0.00 Avg rating—0 Votes

Article ID:	iaor19971053
Country:	France
Volume:	30
Issue:	2
Start Page Number:	127
End Page Number:	142
Publication Date:	Apr 1996
Journal:	RAIRO Operations Research
Authors:	Pferschy U.
Keywords:	bottlenecks

Abstract:

It is shown that the expected value of the optimal solution of an n×n linear bottleneck assignment problem with independently and identically 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²) expected running time is presented.

Reviews

Required fields are marked *. Your email address will not be published.