Efficient Deterministic Bicriteria Approximation Algorithms for k -Submodular Cover Problem

We study the k-Submodular Cover (kSC) problem over a ground set V of size n, where the goal is to find k disjoint subsets of V with minimum cost such that a k-submodular utility function exceeds a given threshold. This problem generalizes the well-known Submodular Cover (SC) problem and has numerous applications in artificial intelligence and combinatorial optimization. However, existing approximation algorithms for kSC may not run in polynomial time. In this work, we propose two bicriteria approximation algorithms that not only improve the performance guarantees but also significantly reduce the query complexity compared to the state-of-the-art algorithms.