提出确定性算法，逼近率突破1-κ/e

A Note On Deterministic Submodular Maximization With Bounded Curvature

• 基于曲率约束的确定性优化方法
• 逼近比达(1-κ_f/e-ε)，优于传统随机算法
• 适合需要可重复结果的场景

我们表明，近期[ Buchbinder and Feldman, FOCS'24]的突破性成果可进一步导出一种确定性$(1-κ_{f}/e-
)$近似算法，用于在拟阵约束下最大化具有曲率$κ_{f}$的子模函数。该结果改进了传统随机算法的逼近性能，且保证了结果的确定性与可复现性。

原文摘要 · Abstract (English)

We show that the recent breakthrough result of [Buchbinder and Feldman, FOCS'24] could further lead to a deterministic $(1-κ_{f}/e-\varepsilon)$-approximate algorithm for maximizing a submodular function with curvature $κ_{f}$ under matroid constraint.

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。