The random linear bottleneck assignment problem
RAIRO - Operations Research - Recherche Opérationnelle (1996)
- Volume: 30, Issue: 2, page 127-142
- ISSN: 0399-0559
Access Full Article
top
How to cite
topPferschy, U.. "The random linear bottleneck assignment problem." RAIRO - Operations Research - Recherche Opérationnelle 30.2 (1996): 127-142. <http://eudml.org/doc/105124>.
@article{Pferschy1996,
author = {Pferschy, U.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {random bottleneck assignment; average case analysis; random graphs; linear bottleneck assignment problem},
language = {eng},
number = {2},
pages = {127-142},
publisher = {EDP-Sciences},
title = {The random linear bottleneck assignment problem},
url = {http://eudml.org/doc/105124},
volume = {30},
year = {1996},
}
TY - JOUR
AU - Pferschy, U.
TI - The random linear bottleneck assignment problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 2
SP - 127
EP - 142
LA - eng
KW - random bottleneck assignment; average case analysis; random graphs; linear bottleneck assignment problem
UR - http://eudml.org/doc/105124
ER -
References
top- 1. M. ABRAMOWITZ and I. A. STEGUN, Handbook of Mathematical functions, Dover Publications, New York, 1965. Zbl0171.38503
- 2. B. BOLLOBÁS, Random Graphs, Academic Press, 1985. Zbl0567.05042MR809996
- 3. B. BOLLOBÁS and A. THOMASON, Random graphs of small order, Random Graphs'83, Annals of Discrete Math., 1985, 28, pp. 47-97. Zbl0588.05040MR860586
- 4. R. E. BURKARD and U. DERIGS, Assignment and Matching Problems: Solution Methods with FORTRAN-Programs, Springer Lecture Notes in Economics and Mathematical Systems, 1980, 184. Zbl0436.90069MR610241
- 5. U. DERIGS, The shortest augmenting path method for solving assignment problems, Annals of Operations Research, 1985, 4, pp. 57-102. MR948014
- 6. U. DERIGS, Programming in networks and graphs, Springer Lectures Notes in Economics and Mathematical Systems, 1988, 300. Zbl0658.90031MR1117224
- 7. P. ERDÖS and A. RÉNYI, On random matrices, Publ. Math. Inst. Hungar. Acad. Sci., 1964, 8, pp. 455-461. Zbl0133.26003MR167496
- 8. J. B. G. FRENK, M. VAN HOUWENINGE and A. H. G. RINNOOY KAN, Order statistics and the linear assignment problem, Report 8609/A, Econometric Institute, Erasmus University, Rotterdam, The Netherlands, 1986. Zbl0636.62008
- 9. H. N. GABOW and R. E. TARJAN, Algorithms for two bottleneck optimization problems, J. of Algorithms, 1988, 9, pp. 411-417. Zbl0653.90087MR955149
- 10. J. E. HOPCROFT and R. M. KARP, An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput, 1973, 2, pp. 225-231. Zbl0266.05114MR337699
- 11. R. M. KARP, An algorithm to solve the m x n assignment problem in expected time O (mn log n), Networks, 1980, 10, pp. 143-152. Zbl0441.68076MR569006
- 12. R. M. KARP, An upper bound on the expected cost of an optimal assignment, Technical report, Computer Sc. Div., Univ. of California, Berkeley, 1984. Zbl0639.90066
- 13. S. LANG, Complex Analysis, Springer, 1985. Zbl0562.30001MR788885
- 14. A. J. LAZARUS, The assignment problem with uniform (0, 1) cost matrix, Master's thesis, Department of Mathematics, Princeton University, 1979.
- 15. B. OLIN, Asymptotic properties of random assignment problems. PhD-thesis, Division of Optimization and Systems Theory, Department of Mathematics, Royal Institute of Technology, Stockholm, 1992. MR2714678
- 16. E. M. PALMER, Graphical Evolution, J. Wiley & Sons, 1985. Zbl0566.05002MR795795
- 17. D. W. WALKUP, On the expected value of a random assignment problem, SIAM J. Comput., 1979, 8, pp. 440-442. Zbl0413.68062MR539262
- 18. D. W. WALKUP, Matchings in random regular bipartite digraphs, Discrete Mathematics, 1980, 31, pp. 59-64. Zbl0438.05031MR578061
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.