提出统一方法，在噪声下仍能保持最优近似率地最大化子模函数。
A Unified Approach to Submodular Maximization Under Noise
- 设计通用元算法，将精确算法转化为抗噪声版本
- 在噪声下实现1-1/e近似率（单调）和1/e近似率（非单调）
- 适用于各类约束，适合研究优化与鲁棒性问题的学者
我们研究在仅能通过噪声值查询接口访问子模函数时的最大化问题。假设噪声查询具有持久性，即对同一集合多次查询返回相同结果。此前工作在基数约束下给出(1-1/e)近似，在任意拟阵约束下给出(1-1/e)/2近似。本文提出一种元算法，可将任何“鲁棒”的精确子模最大化算法转化为噪声环境下的算法，并保持原有近似保证。结合测量连续贪婪算法，获得在拟阵约束下单调情形的(1-1/e)近似、非单调情形的1/e近似；结合双贪婪算法，获得无约束非单调情形的1/2近似。
原文摘要 · Abstract (English)
We consider the problem of maximizing a submodular function with access to a noisy value oracle for the function instead of an exact value oracle. Similar to prior work, we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value. In this model, Hassidim and Singer (2017) design a $(1-1/e)$-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) design a $(1-1/e)/2$-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint. In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a $(1-1/e)$-approximation (resp. $1/e$-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a $1/2$-approximation for unconstrained (non-monotone) submodular maximization under noise.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。