研究在线子模最大化中稳定性对性能的影响，发现稳定解的最优近似率为2/3。
The Cost of Consistency: Submodular Maximization with Constant Recourse
- 限制每步更新次数为常数，分析稳定解的近似性能边界
- 通用单调子模函数下理论最优比为2/3，覆盖函数提升至3/4
- 提出多项式时间随机算法，实现0.51近似，区分确定与随机算法
本文研究在线子模最大化问题中维持解稳定性对近似性能的影响。具体而言，我们关注在每步最多允许常数次更新的前提下，可达到的最佳近似比的理论界限。对于一般单调子模函数，我们证明了紧的$ frac{2}{3}$信息论上界；对于覆盖函数，该上界可提升至$ frac{3}{4}$（同样紧）。由于这两个上界均由非多项式时间算法达成，我们进一步设计了一个多项式时间随机算法，实现了$0.51$-近似。结合先前工作已知的确定性算法信息论下界$ frac{1}{2}$，本工作揭示了确定性与随机算法之间的分离现象，无论在信息论层面还是多项式时间框架下均成立。
原文摘要 · Abstract (English)
In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowed to make at most a constant number of updates per step. We show a tight information-theoretic bound of $\tfrac{2}{3}$ for general monotone submodular functions, and an improved (also tight) bound of $\tfrac{3}{4}$ for coverage functions. Since both these bounds are attained by non poly-time algorithms, we also give a poly-time randomized algorithm that achieves a $0.51$-approximation. Combined with an information-theoretic hardness of $\tfrac{1}{2}$ for deterministic algorithms from prior work, our work thus shows a separation between deterministic and randomized algorithms, both information theoretically and for poly-time algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。