English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study a dynamic and stochastic knapsack problem in which a decision maker is sequentially presented with items arriving according to a Bernoulli process over $n$ discrete time periods. Items have equal rewards and independent weights that are drawn from a known non-negative continuous distribution $F$. The decision maker seeks to maximize the expected total reward of the items that she includes in the knapsack while satisfying a capacity constraint and while making terminal decisions as soon as each item weight is revealed. Under mild regularity conditions on the weight distribution $F$, we prove that the regret---the expected difference between the performance of the best sequential algorithm and that of a prophet who sees all of the weights before making any decision---is, at most, logarithmic in $n$. Our proof is constructive. We devise a reoptimized heuristic that achieves this regret bound.

Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards