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

DOI10.14708/MA.V44I1.817MaRDI QIDQ5357635zbMATH OpenOpenAlexFDO

Authors J. Michael Steele

Publication date 12 September 2017

Published in Mathematica Applicanda (Search for Journal in Brave)

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

zbMATH Keywords

knapsack problemmonotone subsequence problemorder statistic inequalities

Mathematics Subject Classification ID

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

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.

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

Cited in

(8)

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

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)