The Bruss-Robertson Inequality:Elaborations, Extensions, and Applications

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

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

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)

• 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
• Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards
• Sequential selection of a monotone subsequence from a random permutation
• Galton--Watson Processes and Their Role as Building Blocks for Branching Processes

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)