Large deviations in subadditive processes and first-passage percolation
This paper presents a welcome overview on large deviations in subadditive processes. There is particular reference to first-passage percolation, where fuller results are known, and it is shown how these help in the investigation of random electrical networks. The paper also presents some applications of probability theory in operations research. It discusses a recent randomised colouring method of \textit{D. J. A. Welsh} [A randomized algorithm for an NP-complete problem. (to appear)], and the behaviour of the simple greedy colouring algorithm on random graphs. Results on subadditive processes are used to analyse random bin packing problems. (It has recently been noted that elementary martingale inequalities yield rather better results.) For the entire collection see [Zbl 0562.00006].
This page was built for publication: Large deviations in subadditive processes and first-passage percolation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3729748)