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

• Autorzy: J. Michael Steele
• Języki publikacji: EN

Abstrakty

EN

The Bruss-Robertson inequality gives a bound on themaximal number of elements of a random sample whose sum is less than a specifiedvalue, and the extension of that inequality which is given hereneither 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 maksymalna 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 niezaleznoś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.

Słowa kluczowe

EN

order statistic inequalities, knapsack problem, monotone subsequence problem

PL

nierówności dla statystyk rangowych; sekwencyjny problem upakowania; wybór sekwencyjny; markowski problem decyzyjny; proces gałązkowy; równanie Bellman

• Wydawca: Polish Mathematical Society
• Czasopismo: Mathematica Applicanda
• Rocznik: 2015
• Tom: 44
• Numer: 1

Daty

wydano

2016

online

2015-11-17

Twórcy

autor

J. Michael Steele

Identyfikatory

DOI

10.14708/ma.v44i1.817