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/

Zendy Plus

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

Zendy Tools

Zendy Open

The stochastic knapsack problem is the stochastic variant of the classicalknapsack problem in which the algorithm designer is given a a knapsack with agiven capacity and a collection of items where each item is associated with aprofit and a probability distribution on its size. The goal is to select asubset of items with maximum profit and violate the capacity constraint withprobability at most $p$ (referred to as the overflow probability). Whileseveral approximation algorithms have been developed for this problem, most ofthese algorithms relax the capacity constraint of the knapsack. In this paper,we design efficient approximation schemes for this problem without relaxing thecapacity constraint.  (i) Our first result is in the case when item sizes are Bernoulli randomvariables. In this case, we design a (nearly) fully polynomial timeapproximation scheme (FPTAS) which only relaxes the overflow probability. (ii)Our second result generalizes the first result to the case when all the itemsizes are supported on a (common) set of constant size. (iii) Our third resultis in the case when item sizes are so-called "hypercontractive" randomvariables i.e., random variables whose second and fourth moments are withinconstant factors of each other. In other words, the kurtosis of the randomvariable is upper bounded by a constant.  Crucially, all of our algorithms meet the capacity constraint exactly, aresult which was previously known only when the item sizes were Poisson orGaussian random variables. Our results rely on new connections between Booleanfunction analysis and stochastic optimization. We believe that these ideas andtechniques may prove to be useful in other stochastic optimization problems aswell.

Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack