## Stochastic Submodular Cover with Limited Adaptivity

Authors:
Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna.

Conference:
The 30th ACM-SIAM Symposium on Discrete Algorithms (SODA'19)

This paper resolves an open question raised
by Goemans and Vondrak in [GV'06] on the adaptivity
gap of the stochastic set cover problem.

Abstract:
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 ⊆ 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.

A fully adaptive algorithm for stochastic sub- modular cover chooses an item to realize and based on its realization, decides which item to realize next. A non-adaptive algorithm on the other hand needs to choose a permutation of items beforehand and realize them one by one in the order specified by this permutation until the function value reaches Q. The cost of the algorithm in both case is the number (or costs) of items realized by the algorithm. It is not difficult to show that even for the coverage function there exist instances where the expected cost of a fully adaptive algorithm and a non-adaptive algorithm are separated by Ω(Q). This strong separation, often referred to as the adaptivity gap, is in sharp contrast to the separations observed in the framework of stochastic packing problems where the performance gap for many natural problem is close to the poly-time approximability of the non-stochastic version of the problem. Motivated by this striking gap between the power of adaptive and non-adaptive algorithms, we consider the following question in this work: does one need full power of adaptivity to obtain a near-optimal solution to stochastic submodular cover? In particular, how does the performance guarantees change when an algorithm interpolates between these two extremes using a few rounds of adaptivity.

Towards this end, we define an r-round adaptive algorithm to be an algorithm that chooses a permutation of all available items in each round k ∈ [r], and a threshold τ_k, and realizes items in the order specified by the permutation until the function value is at least τ_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 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 Ω(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. Thus our work shows that logarithmic rounds of adaptivity are necessary and sufficient to obtain near-optimal solutions to the stochastic submodular cover problem, and even few rounds of adaptivity are sufficient to sharply reduce the adaptivity gap.

A fully adaptive algorithm for stochastic sub- modular cover chooses an item to realize and based on its realization, decides which item to realize next. A non-adaptive algorithm on the other hand needs to choose a permutation of items beforehand and realize them one by one in the order specified by this permutation until the function value reaches Q. The cost of the algorithm in both case is the number (or costs) of items realized by the algorithm. It is not difficult to show that even for the coverage function there exist instances where the expected cost of a fully adaptive algorithm and a non-adaptive algorithm are separated by Ω(Q). This strong separation, often referred to as the adaptivity gap, is in sharp contrast to the separations observed in the framework of stochastic packing problems where the performance gap for many natural problem is close to the poly-time approximability of the non-stochastic version of the problem. Motivated by this striking gap between the power of adaptive and non-adaptive algorithms, we consider the following question in this work: does one need full power of adaptivity to obtain a near-optimal solution to stochastic submodular cover? In particular, how does the performance guarantees change when an algorithm interpolates between these two extremes using a few rounds of adaptivity.

Towards this end, we define an r-round adaptive algorithm to be an algorithm that chooses a permutation of all available items in each round k ∈ [r], and a threshold τ_k, and realizes items in the order specified by the permutation until the function value is at least τ_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 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 Ω(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. Thus our work shows that logarithmic rounds of adaptivity are necessary and sufficient to obtain near-optimal solutions to the stochastic submodular cover problem, and even few rounds of adaptivity are sufficient to sharply reduce the adaptivity gap.

Conference version:
[PDF]

Full version:
[arXiv]

BibTex:
[DBLP]