Key points are not available for this paper at this time.
In this paper, we study the Minimum Cost Submodular Cover (MCSC) problem over the ground set of size Formula: see text, which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a Formula: see text-bicriteria approximation solution within Formula: see text adaptive complexity, where Formula: see text are fixed parameters. Our algorithm requires Formula: see text query complexity, however, it can reduce to Formula: see text instead while retaining a low adaptive complexity of Formula: see text. Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem.
Nguyen et al. (Fri,) studied this question.