Abstract
The Stochastic Set Cover (SSC) problem extends the classical NP-hard Set Cover problem into environments where the elements covered by a set are only revealed after the set is selected. While previous research established a quadratic-logarithmic approximation ratio for the adaptive greedy algorithm, this paper demonstrates a tighter bound. We show that the adaptive greedy algorithm achieves an approximation ratio of $H(|B|)$, where $|B|$ is the size of the ground set. This result matches the performance of the greedy algorithm in the deterministic setting and simplifies the theoretical landscape of stochastic combinatorial optimization.
Introduction
In the deterministic Set Cover problem, the goal is to select a collection of sets that cover all elements in a ground set at minimum cost. In many real-world scenarios, however, the coverage provided by a specific action is uncertain. The Stochastic Set Cover (SSC) problem models this uncertainty by treating each "item" (the stochastic equivalent of a set) as a random variable. When an item is selected and its cost is paid, its actual coverage—a subset of the ground set—is revealed.
Because the outcome of each selection is unknown until it occurs, an algorithm must be adaptive: subsequent choices must be informed by the elements already covered. The objective is to minimize the total expected cost to achieve full coverage. This paper revisits the adaptive greedy algorithm, a natural heuristic for this problem, and provides a significantly improved theoretical analysis of its performance.
The Adaptive Greedy Algorithm
The adaptive greedy algorithm operates by making locally optimal decisions at each step. Given a current state—defined by the set of elements already covered—the algorithm evaluates each available item based on its "unit price." The unit price is defined as:
$$\text{Unit Price} = \frac{\text{Cost of Item}}{\mathbb{E}[\text{Number of new elements covered}]}$$
The algorithm selects the item with the lowest unit price, observes the revealed elements, and repeats the process until the entire ground set $B$ is covered.
Theoretical Contributions
The primary contribution of this work is the proof that the adaptive greedy algorithm achieves an approximation ratio of $H(|B|)$, where $H(n) = \sum_{i=1}^n \frac{1}{i} \approx \ln n + 0.577$.
Closing the Gap
Prior to this work, the best-known bound for the adaptive greedy algorithm in the stochastic setting was $(1 + \ln |B|)^2$, established by Golovin and Krause (2011). By employing a more sophisticated probabilistic accounting method, this paper proves that the additional squaring is unnecessary. This aligns the stochastic bound with the well-known $H(n)$ bound for the deterministic greedy algorithm.
Handling Imperfect Coverage
The paper distinguishes between two scenarios:
- Perfect Coverage: Every element in the ground set is guaranteed to be covered if all items are selected.
- Imperfect Coverage: There is a non-zero probability that some elements cannot be covered by any available item.
For the imperfect case, the author introduces a reduction technique. By transforming the problem into a bipartite graph where the ground set is redefined as the set of all possible item-element pairs $\mathcal{E}$ that could occur, the author extends the $H(|B|)$ bound to $H(|\mathcal{E}|)$.
Key Insights
The analysis relies on the property that both the greedy algorithm and the optimal adaptive strategy are "oblivious" to the internal state of an item until it is evaluated. This allows for the treatment of conditional state distributions as independent, which simplifies the complex dependencies inherent in stochastic processes. The proof compares the expected price assigned to each element under the greedy strategy against the expected cost incurred by an optimal policy.
Discussion and Limitations
While this paper provides a tight bound relative to the size of the ground set, an open question remains regarding the "cardinality" bound. In deterministic set cover, the greedy algorithm is also bounded by $H(\ell)$, where $\ell$ is the maximum size of any single set. Whether a similar bound exists for the stochastic version—based on the maximum number of elements an item can cover ($n$) rather than the total ground set size ($|B|$)—is currently unknown.
Additionally, the practical implementation of the algorithm depends on the ability to efficiently calculate the expected number of new elements. If the probability distributions governing item outcomes are highly complex, calculating the denominator of the unit price may become a computational bottleneck.
Conclusion
This research provides a definitive analysis of the adaptive greedy algorithm for Stochastic Set Cover. By proving a logarithmic approximation ratio, the paper demonstrates that the greedy approach is as effective in stochastic environments as it is in deterministic ones, providing a robust theoretical foundation for its use in adaptive decision-making.
Summary updated