Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908624631103488 |
|---|---|
| author | Nguyen, Hue T. Tran, Tan D. Giang, Nguyen Long Pham, Canh V. |
| author_facet | Nguyen, Hue T. Tran, Tan D. Giang, Nguyen Long Pham, Canh V. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00869 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem Nguyen, Hue T. Tran, Tan D. Giang, Nguyen Long Pham, Canh V. Data Structures and Algorithms Artificial Intelligence 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. |
| title | Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2511.00869 |