将非单调子模最大化算法的近似率提升至7+ε，保持低自适应复杂度。
Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint
- 设计交替阈值框架，分轮构建两组不相交解
- 在O(log n)自适应轮数下实现7+ε近似比
- 适用于收益最大化、图像摘要等场景
本文提出一种高效并行算法，用于解决规模为n的基集上带有背包约束的非单调子模最大化问题。算法将现有并行方法的最佳近似因子从8+ε提升至7+ε，且自适应复杂度为O(log n)。核心思想是构建新的交替阈值算法框架：在常数轮次内交替生成两组互不相交的候选解，从而在不增加自适应复杂度的前提下提升解的质量。在收益最大化、图像摘要和最大权割三个应用上的大量实验表明，该算法不仅显著提高解质量，且自适应轮数与当前最优算法相当。
原文摘要 · Abstract (English)
This work proposes an efficient parallel algorithm for non-monotone submodular maximization under a knapsack constraint problem over the ground set of size $n$. Our algorithm improves the best approximation factor of the existing parallel one from $8+ε$ to $7+ε$ with $O(\log n)$ adaptive complexity. The key idea of our approach is to create a new alternate threshold algorithmic framework. This strategy alternately constructs two disjoint candidate solutions within a constant number of sequence rounds. Then, the algorithm boosts solution quality without sacrificing the adaptive complexity. Extensive experimental studies on three applications, Revenue Maximization, Image Summarization, and Maximum Weighted Cut, show that our algorithm not only significantly increases solution quality but also requires comparative adaptivity to state-of-the-art algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。