The Bruss-Robertson inequality: elaborations, extensions, and applications

DOI10.14708/MA.V44I1.817zbMATH Open1370.60012arXiv1510.00843OpenAlexW2963240966MaRDI QIDQ5357635FDOQ5357635

Authors: J. Michael Steele 

Publication date: 12 September 2017

Published in: Mathematica Applicanda (Search for Journal in Brave)

Abstract: The Bruss-Robertson inequality gives a bound on the maximal number of elements of a random sample whose sum is less than a specified value, and the extension of that inequality which is given here neither requires the independence of the summands nor requires the equality of their marginal distributions. A review is also given of the applications of the Bruss-Robertson inequality, especially the applications to problems of combinatorial optimization such as the sequential knapsack problem and the sequential monotone subsequence selection problem.

Full work available at URL: https://arxiv.org/abs/1510.00843

Recommendations

• The BRS-inequality and its applications
• A note on the selection of random variables under a sum constraint
• An inequality for the sum of independent bounded random variables
• Inequalities for one maximum of partial sums of random variables obtained by using subadditive functions
• A probabilistic inequality for sums of bounded symmetric independent random variables

zbMATH Keywords

knapsack problemmonotone subsequence problemorder statistic inequalities

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)

Cited In (7)

• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• Galton-Watson processes and their role as building blocks for branching processes
• A new method for generating Bonferroni-type inequalities by iteration
• The BRS-inequality and its applications
• The Bruss–Robertson–Steele inequality
• On sequential selection and a first passage problem for the Poisson process
• Sequential selection of a monotone subsequence from a random permutation

This page was built for publication: The Bruss-Robertson inequality: elaborations, extensions, and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5357635)