Probability and statisitics in the service of computer science: illustrations using the assignment problem
- 1 January 1990
- journal article
- research article
- Published by Taylor & Francis in Communications in Statistics - Theory and Methods
- Vol. 19 (11) , 4315-4329
- https://doi.org/10.1080/03610929008830444
Abstract
Recent work on the assignment problem is surveyed with the aim of illustrating the contribution that stochastic thinking can make to problems of interest to computer scientists. The assignment problem is thus examined in connection with the analysis of greedy algorithms, marriage lemmas, linear programming with random costs, randomization based matching, stochastic programming, and statistical mechanics. (The survey is based on the invited presentation given during the “Statistics Days at FSU” in March 1990.)Keywords
This publication has 17 references indexed in Scilit:
- A Lower Bound on the Expected Cost of an Optimal AssignmentMathematics of Operations Research, 1993
- On the solution of the random link matching problemsJournal de Physique, 1987
- On optimal matchingsCombinatorica, 1984
- Optimization by Simulated AnnealingScience, 1983
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980
- Algorithm and Average-value Bounds for Assignment ProblemsIBM Journal of Research and Development, 1969
- On Approximation Methods for the Assignment ProblemJournal of the ACM, 1962
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959
- The Marriage ProblemAmerican Journal of Mathematics, 1950
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935