Price of dependence: stochastic submodular maximization with dependent items

DOI10.1007/S10878-019-00470-6MaRDI QIDQ2292144zbMATH OpenOpenAlexFDO

Authors Shaojie Tang

Publication date 3 February 2020

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.09719

zbMATH Keywords

stochastic optimizationapproximate algorithmsdependent variablessubmodular maximization

Mathematics Subject Classification ID

Randomized algorithms (68W20) Stochastic programming (90C15) Approximation algorithms (68W25)

Abstract: In this paper, we study the stochastic submodular maximization problem with dependent items subject to packing constraints such as matroid and knapsack constraints. The input of our problem is a finite set of items, and each item is 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 utility function over items and states, and our objective is to select a group of items adaptively so as to maximize the expected utility. Previous studies on stochastic submodular maximization often assume that items' states are independent, however, this assumption may not hold in general. This motivates us to study the stochastic submodular maximization problem with dependent items. We first introduce the concept of emph{degree of independence} to capture the degree to which one item's state is dependent on others'. Then we propose a non-adaptive policy that approximates the optimal adaptive policy within a factor of $alpha(1-e^{-frackappa2+frackappa18m^2}-frackappa+23mkappa)$ 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 also analyze the adaptivity gap, i.e., the ratio of the values of best adaptive policy and best non-adaptive policy, of our problem with prefix-closed constraints.

Recommendations

• Stochastic submodular probing with state-dependent costs
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• Adaptivity gaps for stochastic probing: submodular and XOS functions
• The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
• Stochastic submodular cover with limited adaptivity

Cites work

• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Adaptivity gaps for stochastic probing: submodular and XOS functions
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• Maximizing a monotone submodular function subject to a matroid constraint
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular stochastic probing on matroids

Cited in

(8)

• Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
• Constrained stochastic submodular maximization with state-dependent costs
• Adaptive robust submodular optimization and beyond
• The dependent doors problem: an investigation into sequential decisions without feedback
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
• Partial-monotone adaptive submodular maximization
• Stochastic submodular probing with state-dependent costs

This page was built for publication: Price of dependence: stochastic submodular maximization with dependent items

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292144)