提出首个动态子模优化的高效稳定算法框架
A General Framework for Dynamic Consistent Submodular Maximization
- 设计通用框架应对插入删除混合场景
- 实现常数倍近似，调整次数为亚线性
- 适用于约束优化，适合在线系统
一致性是动态子模最大化中的关键性质，要求算法在任意时刻保持近优解，且每步调整量小。已有工作仅研究仅插入场景，建立了基数约束下的上下界。本文首次在全动态设置（含插入与删除）下提出通用算法框架，并首次获得常数因子近似解，同时实现亚线性一致性。对于基数约束，给出(1/2 - O(ε))近似，一致性为O(1/ε²)；对于秩k的拟阵约束，构造出(1/4 - O(ε))近似，一致性为O(log k / ε²)。
原文摘要 · Abstract (English)
Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of $n$ insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a $\frac 12 - O(\varepsilon)$ approximation that is $O\left(\frac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\frac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\frac{\log k}{\varepsilon^2}\right)$ consistent.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。