本文从鲁棒优化的角度重新审视了连续版本的预算分配或二分图影响最大化问题,并利用与连续次模函数的联系以及求解受约束子模最小化问题的方法精确地解决了这个非凸问题。
Feb, 2017
本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了 5.83 近似和 O (nlogn) 时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。
Jul, 2020
研究了 Greedy 算法在非子模不减集函数基数约束最大化中的性能,并证明了在一些重要的非子模函数如贝叶斯 A - 最优目标函数中,该算法具有很强的经验性能。我们以广义曲率 α 和子模性比率 γ 的组合为特点,证明了其理论保证,特别地,对于基数约束最大化,我们证明了 Greedy 算法具有紧密的近似保证为 1/α(1-e^(-γα))。另外,我们还限制了在几个重要的真实世界目标中子模性比率和曲率,包括贝叶斯 A - 最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。
Mar, 2017
本文提出自适应子模性的概念,将子模集函数推广到自适应策略,并使用自适应贪心算法解决具有不确定性结果的随机优化问题,通过使用懒惰评估方法显著加快了算法。通过提供子模目标的几个示例,包括传感器放置,病毒营销和主动学习,证明了自适应子模性的实用性。
Mar, 2010
研究了随机预算多轮次子模最大化问题,提出了一个动态规划算法,解决了单轮优化问题,也给出了一个简单贪婪算法,可近似求解问题。
Apr, 2024
本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值,其中距离次模性的距离由参数 γ 衡量,该算法在实践中表现良好,并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
Jul, 2017
通过定义锐度作为子模函数改善贪心算法性能的候选解释,本文探讨了贪心算法在最大化单调子模函数下的性能问题,显示子模函数的锐度影响贪心算法的表现,通过计算实验和理论结果,支持本文的说法。
Feb, 2020
本文提出了一种能够动态地为信息源进行排序,同时又能保证重复信息的减少不会影响子模函数的最优化问题算法,并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。
Jul, 2014
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
研究使用机会约束的子模型优化问题,探讨贪心算法在应用对 Chernoff 边界进行约束违规估计的替代函数后,能高效地获得高品质解,同时在社交网络问题中也能保持有效性。
Nov, 2019