zbMATH — the first resource for mathematics

Distribution-free bounds on the expectation of the maximum with scheduling applications. (English) Zbl 0715.90068
Summary: Let \(X_ 1,X_ 2,...,X_ n\) be independent random variables with a fixed, common parent distribution for which the p-th moment \(E| X|^ p\) is defined. Then the maximum order statistic \(X_{(n)}\) grows at a rate that is \(o(n^{1/p})\) in expectation, in probability and a.e. Explicit bounds of this order can be given for \(EX_{(n)}\) in terms of the moments of X. Thus the expectation of the extreme grows slowly with the sample size. This observation is applied to the speed-up realized by parallel computation, and to the performance of scheduling policies.

90B35 Deterministic scheduling theory in operations research
68W15 Distributed algorithms
Full Text: DOI
[1] Barlow, R.E.; Proschan, F., Statistical theory of reliability and life testing: probability models, (1975), Holt, Rinehart and Winston New York · Zbl 0379.62080
[2] Bruno, J.L.; Downey, P.J., Probabilistic bounds on the performance of List scheduling, SIAM J. comput., 15, 2, 409-417, (1986) · Zbl 0595.68037
[3] Chung, K.L., A course in probability theory, (1974), Academic Press New York · Zbl 0159.45701
[4] Coffman, E.G., Computer and job-shop scheduling theory, (1976), Wiley New York · Zbl 0359.90031
[5] David, H.A., Order statistics, (1970), Wiley New York · Zbl 0223.62057
[6] Dempster, M.A.H.; Fisher, M.L.; Jansen, L.; Lageweg, B.J.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Analysis of heuristics for stochastic programming: results for hierarchical scheduling problems, Math. oper. res., 8, 4, 525-537, (1983) · Zbl 0532.90078
[7] Downey, P.J.; Maier, R.S., Logarithmic moment bounds for extreme order statistics, ()
[8] Freedman, D., Markov chains, (1983), Springer-Verlag New York · Zbl 0212.49801
[9] Galambos, J., The asymptotic theory of extreme order statistics, (1978), Wiley New York · Zbl 0381.62039
[10] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco, CA · Zbl 0411.68039
[11] Graham, R.L., Bounds on the performance of scheduling algorithms, () · Zbl 0188.23101
[12] Kleinrock, L., ()
[13] Kung, H.T., Synchronized and asynchronous parallel algorithms for multiprocessors, () · Zbl 0368.68039
[14] Lenstra, J.K.; Rinnooy Kan, A.H.G.; Stougie, L., A framework for the probabilistic analysis of hierarchical planning systems, Ann. oper. res., 1, 23-42, (1984) · Zbl 0671.90060
[15] Loève, M., Probability theory, (1963), D. Van Nostrand Princeton, NJ · Zbl 0108.14202
[16] Pickands, J., Moment convergence of sample extremes, Ann. math. statist., 39, 3, 881-889, (1968) · Zbl 0176.48804
[17] Reiss, R.-D., Approximate distributions of order statistics, (1989), Springer-Verlag New York · Zbl 0682.62009
[18] Shorack, G.R.; Wellner, J.A., Empirical processes with applications to statistics, (1986), Wiley New York · Zbl 1170.62365
[19] G. Weiss, “Approximation results in parallel machines stochastic scheduling”, to appear in Ann. Oper. Res.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.