{"ID":2846991,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.00869","arxiv_id":"2511.00869","title":"Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem","abstract":"We study the $k$-Submodular Cover ($kSC$) problem, a natural generalization of the classical Submodular Cover problem that arises in artificial intelligence and combinatorial optimization tasks such as influence maximization, resource allocation, and sensor placement. Existing algorithms for $\\kSC$ often provide weak approximation guarantees or incur prohibitively high query complexity. To overcome these limitations, we propose a \\textit{Fast Stochastic Greedy} algorithm that achieves strong bicriteria approximation while substantially lowering query complexity compared to state-of-the-art methods. Our approach dramatically reduces the number of function evaluations, making it highly scalable and practical for large-scale real-world AI applications where efficiency is essential.","short_abstract":"We study the $k$-Submodular Cover ($kSC$) problem, a natural generalization of the classical Submodular Cover problem that arises in artificial intelligence and combinatorial optimization tasks such as influence maximization, resource allocation, and sensor placement. Existing algorithms for $\\kSC$ often provide weak a...","url_abs":"https://arxiv.org/abs/2511.00869","url_pdf":"https://arxiv.org/pdf/2511.00869v1","authors":"[\"Hue T. Nguyen\",\"Tan D. Tran\",\"Nguyen Long Giang\",\"Canh V. Pham\"]","published":"2025-11-02T09:39:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.AI\"]","methods":"[]","has_code":false}