关键词monotone submodular function
搜索结果 - 10
- 动态非单调次模最大化
我们通过降低一个非单调子模函数的约束条件 k 到同样约束条件 k 下最大化一个单调子模函数，肯定回答了陈和彭提出的问题，并得到了第一个动态算法来解决非单调子模函数最大化问题。我们的算法保持了一个 (8+ε) 近似的解，并且每次更新使用预期平 - 约束次模优化问题的全动态算法
本研究在完全动态的环境下，旨在最大化基数约束下的单调子模函数，研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法，并结合经验研究证明了算法性能的优越性。
- 全息子模流处理：紧密逼近、最小内存和低自适应复杂度
本文讨论了在 streaming setting 下最大化单调次模函数，并给出了一种新的算法 Sieve-Streaming++ 以及其扩展到多源 streaming setting 的方案，最终将该算法应用于 twitter 和 yout - 非猜测式的子模和线性和的最大化
本研究提出了一种新颖的加权技术算法，以解决最大化单调子模函数和线性函数总值的问题， 该问题在一般可解的多面体约束条件下， 相对于 Sviridenko 等人 2017 年提出的算法推断步骤更为简单，但其保持了相同的近似保证。
- 具有近似最优的适应性和查询复杂度的子模最大化
本文研究自适应子模型优化的适应性和查询复杂度，提出了适用于最大基数约束的单调子模型函数的分布式算法，并将其推广到子模型覆盖问题。
- 近似最优化的子模最大化算法及其近线性时间自适应实现
本文研究了在满足基数约束的条件下，最大化单调子模函数的逼近保证和适应性之间的权衡问题。我们给出了第一个使用 O（lnn /epsilon^2）轮适应性实现 1-1 /e-epsilon 逼近的算法，同时算法的函数评估次数和额外运行时间分别为 - 噪音下的次模优化
本文考虑在噪声下最大化单调子模函数，探讨在噪声和误差存在的情况下，是否能获得算法的可证明保证，结论是对于基数约束 k>=2 的函数，有一个近似算法，其近似比例任意接近 1-1/e; 对于基数约束 k=1，有一种算法，其近似比率任意接近于 1 - AAAI懒惰比贪心更懒惰
本文提出了一种线性时间算法 STOCHASTIC-GREEDY 用于求解一般性单调子模函数最大化问题，旨在实现对数据的概括，比传统算法 lazy greedy 更快且表现基本一致。
- 模模块极值相遇流式计算：匹配，拟阵等
本文研究了最大子模函数匹配问题，给出了两种空间复杂度均为 O (nlogn) 的半流算法，并探讨了最大加权匹配和多重矩阵交叉的相似性，以求得更普适的解决方案。
- 相关差异机制设计
本文介绍了如何通过单序列挂牌策略（SPMs）来进行拍卖，尤其是在由某些环境约束下，可以与最优机制相媲美。通过与相关差的概念建立联系，本文相对于随机集合的单调子模函数期望来解释了拍卖机制表现的性能，并表明某些 SPM 可以通过很好的固定因子来