Adaptivity gaps for stochastic probing: submodular and XOS functions

DOI10.1137/1.9781611974782.111MaRDI QIDQ4575854zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Viswanath Nagarajan, Sahil Singla

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

Abstract: Suppose we are given a submodular function $f$ over a set of elements, and we want to maximize its value subject to certain constraints. Good approximation algorithms are known for such problems under both monotone and non-monotone submodular functions. We consider these problems in a stochastic setting, where elements are not all active and we can only get value from active elements. Each element $e$ is active independently with some known probability $p_e$, but we don't know the element's status emph{a priori}. We find it out only when we emph{probe} the element $e$---probing reveals whether it's active or not, whereafter we can use this information to decide which other elements to probe. Eventually, if we have a probed set $S$ and a subset $extactive(S)$ of active elements in $S$, we can pick any $Tsubseteqextactive(S)$ and get value $f(T)$. Moreover, the sequence of elements we probe must satisfy a given emph{prefix-closed constraint}---e.g., these may be given by a matroid, or an orienteering constraint, or deadline, or precedence constraint, or an arbitrary downward-closed constraint---if we can probe some sequence of elements we can probe any prefix of it. What is a good strategy to probe elements to maximize the expected value? In this paper we study the gap between adaptive and non-adaptive strategies for $f$ being a submodular or a fractionally subadditive (XOS) function. If this gap is small, we can focus on finding good non-adaptive strategies instead, which are easier to find as well as to represent. We show that the adaptivity gap is a constant for monotone and non-monotone submodular functions, and logarithmic for XOS functions of small emph{width}. These bounds are nearly tight. Our techniques show new ways of arguing about the optimal adaptive decision tree for stochastic problems.

Recommendations

• Submodular stochastic probing on matroids
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• Submodular stochastic probing on matroids
• Algorithms and adaptivity gaps for stochastic probing
• Stochastic submodular cover with limited adaptivity

Cited in

(27)

• Adaptive robust submodular optimization and beyond
• Scheduling with a processing time oracle
• Non-adaptive stochastic score classification and explainable halfspace evaluation
• Stochastic packing integer programs with few queries
• Price of dependence: stochastic submodular maximization with dependent items
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• Submodular stochastic probing on matroids
• Submodular stochastic probing on matroids
• Algorithms and adaptivity gaps for stochastic probing
• Tight approximation for unconstrained XOS maximization
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Approximation algorithms for stochastic k-TSP
• Submodular maximization with uncertain knapsack capacity
• Stochastic submodular cover with limited adaptivity
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Stochastic submodular probing with state-dependent costs
• Query minimization under stochastic uncertainty
• Better bounds on the adaptivity gap of influence maximization under full-adoption feedback
• Adaptivity gaps for the stochastic Boolean function evaluation problem
• Stochastic Probing with Increasing Precision
• Order-competitive ratio
• A prophet inequality based approach to the adaptive ProbeTopK problem
• Improved approximation factor for adaptive influence maximization via simple greedy strategies
• Identifying approximate minimizers under stochastic uncertainity
• New results on a general class of minimum norm optimization problems
• Bayesian probing on graphs

This page was built for publication: Adaptivity gaps for stochastic probing: submodular and XOS functions

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