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. 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.
PL
Nierówność Bruss-Robertson szacuje maksymalną liczbę elementów w próbie, której suma jest ograniczona przez zadaną liczbę. Uogólnienia tej nierówności podane w tej pracy nie wymagają założenia niezależności składników sumy ani tego, by były o tym samym rozkładzie. Podano także przegląd zastosowań nierówności Brussa-Robertsona, a zwłaszcza zastosowania do problemów kombinatorycznych, takich jak sekwencyjny problem upakowania i wybór monotonicznego podciągu.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.