Price of dependence: stochastic submodular maximization with dependent items

DOI10.1007/S10878-019-00470-6zbMATH Open1437.90117arXiv1905.09719OpenAlexW2982703496MaRDI QIDQ2292144FDOQ2292144

Authors: Shaojie Tang 

Publication date: 3 February 2020

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

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.

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

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

zbMATH Keywords

stochastic optimizationapproximate algorithmsdependent variablessubmodular maximization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)