提出快速随机贪心算法，高效解决k-子模覆盖问题
Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
- 基于随机贪心策略，大幅减少函数评估次数
- 在保证强近似比的同时，查询复杂度显著低于现有方法
- 适合大规模AI场景下的高效资源分配与传感器部署
我们研究了k-子模覆盖（kSC）问题，这是经典子模覆盖问题的自然推广，常见于人工智能与组合优化任务中，如影响力最大化、资源分配和传感器部署。现有kSC算法通常近似保证较弱或查询复杂度过高。为此，我们提出一种快速随机贪心算法，在保持强双准则近似性能的同时，相比最先进的方法大幅降低查询复杂度。该方法显著减少了函数评估次数，使其在需要高效率的大规模真实世界AI应用中具备高度可扩展性和实用性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。