Stochastic Submodular Cover with Limited Adaptivity
Stochastic Submodular Cover with Limited Adaptivity
复制标题
自适应有限的随机子模覆盖
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Khanna
中科院分区：
文献类型：
--
作者：
Arpit Agarwal;Sepehr Assadi;S. Khanna
In the submodular cover problem, we are given a non-negative monotone submodular function $f$ over a ground set $E$ of items, and the goal is to choose a smallest subset $S \subseteq E$ such that $f(S) = Q$ where $Q = f(E)$. In the stochastic version of the problem, we are given $m$ stochastic items which are different random variables that independently realize to some item in $E$, and the goal is to find a smallest set of stochastic items whose realization $R$ satisfies $f(R) = Q$. The problem captures as a special case the stochastic set cover problem and more generally, stochastic covering integer programs.
We define an $r$-round adaptive algorithm to be an algorithm that chooses a permutation of all available items in each round $k \in [r]$, and a threshold $\tau_k$, and realizes items in the order specified by the permutation until the function value is at least $\tau_k$. The permutation for each round $k$ is chosen adaptively based on the realization in the previous rounds, but the ordering inside each round remains fixed regardless of the realizations seen inside the round. Our main result is that for any integer $r$, there exists a poly-time $r$-round adaptive algorithm for stochastic submodular cover whose expected cost is $\tilde{O}(Q^{{1}/{r}})$ times the expected cost of a fully adaptive algorithm. Prior to our work, such a result was not known even for the case of $r=1$ and when $f$ is the coverage function. On the other hand, we show that for any $r$, there exist instances of the stochastic submodular cover problem where no $r$-round adaptive algorithm can achieve better than $\Omega(Q^{{1}/{r}})$ approximation to the expected cost of a fully adaptive algorithm. Our lower bound result holds even for coverage function and for algorithms with unbounded computational power.
In the submodular cover problem, we are given a non-negative monotone submodular function $f$ over a ground set $E$ of items, and the goal is to choose a smallest subset $S \subseteq E$ such that $f(S) = Q$ where $Q = f(E)$. In the stochastic version of the problem, we are given $m$ stochastic items which are different random variables that independently realize to some item in $E$, and the goal is to find a smallest set of stochastic items whose realization $R$ satisfies $f(R) = Q$. The problem captures as a special case the stochastic set cover problem and more generally, stochastic covering integer programs.
We define an $r$-round adaptive algorithm to be an algorithm that chooses a permutation of all available items in each round $k \in [r]$, and a threshold $\tau_k$, and realizes items in the order specified by the permutation until the function value is at least $\tau_k$. The permutation for each round $k$ is chosen adaptively based on the realization in the previous rounds, but the ordering inside each round remains fixed regardless of the realizations seen inside the round. Our main result is that for any integer $r$, there exists a poly-time $r$-round adaptive algorithm for stochastic submodular cover whose expected cost is $\tilde{O}(Q^{{1}/{r}})$ times the expected cost of a fully adaptive algorithm. Prior to our work, such a result was not known even for the case of $r=1$ and when $f$ is the coverage function. On the other hand, we show that for any $r$, there exist instances of the stochastic submodular cover problem where no $r$-round adaptive algorithm can achieve better than $\Omega(Q^{{1}/{r}})$ approximation to the expected cost of a fully adaptive algorithm. Our lower bound result holds even for coverage function and for algorithms with unbounded computational power.
DOI：
10.1137/1.9781611975482.19
发表时间：
2018-04
期刊：
--
影响因子：
--
作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
通讯作者：
Eric Balkanski;A. Rubinstein;Yaron Singer