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

In this paper, we study the stochastic submodular maximization problem withdependent items subject to packing constraints such as matroid and knapsackconstraints. The input of our problem is a finite set of items, and each itemis in a particular state from a set of possible states. After picking an item,we are able to observe its state. We assume a monotone and submodular utilityfunction over items and states, and our objective is to select a group of itemsadaptively so as to maximize the expected utility. Previous studies onstochastic submodular maximization often assume that items' states areindependent, however, this assumption may not hold in general. This motivatesus to study the stochastic submodular maximization problem with dependentitems. We first introduce the concept of \emph{degree of independence} tocapture the degree to which one item's state is dependent on others'. Then wepropose a non-adaptive policy that approximates the optimal adaptive policywithin a factor of$\alpha(1-e^{-\frac{\kappa}{2}+\frac{\kappa}{18m^2}}-\frac{\kappa+2}{3m\kappa})$where the value of $\alpha$ is depending on the type of constraints, e.g.,$\alpha=1$ for matroid constraint, $\kappa$ is the degree of independence,e.g., $\kappa=1$ for independent items, and $m$ is the number of items. We alsoanalyze the adaptivity gap, i.e., the ratio of the values of best adaptivepolicy and best non-adaptive policy, of our problem with prefix-closedconstraints.

Price of Dependence: Stochastic Submodular Maximization with Dependent Items