概率约束次模函数的优化
本文研究了确定性设定中的概率约束子模优化问题,提出了一种新的分析方法,并提供了贪心算法来近似求解最优解。在实验中,演示了算法在几个最大覆盖问题和影响力最大化问题上的有效性。
Sep, 2023
本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数(子模覆盖)和在满足子模上限的约束条件下最大化子模函数(子模背包)。我们将这些问题表述为约束优化问题,并获得许多有界逼近保证。此外,我们证明了这两个问题的紧密关联,并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后,我们通过实验证明了本文算法的效果和良好的可扩展性。
Nov, 2013
本文从鲁棒优化的角度重新审视了连续版本的预算分配或二分图影响最大化问题,并利用与连续次模函数的联系以及求解受约束子模最小化问题的方法精确地解决了这个非凸问题。
Feb, 2017
通过直接优化偏差和方差的组合,该研究通过展示如何进行具有理论保证的高效算法,从而在次模函数中进行分布式鲁棒优化(DRO),从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。
Feb, 2018
基于采样的方法用于直接评估机会约束,研究结果表明,采用不同评估方法的算法性能是可比较的,而采用基于采样的方法的 ASW-GSEMO 算法优于其他算法。
Apr, 2024
该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化,通过将扩展线性化处理并通过向上投影处理,得到离散解,针对加权覆盖函数进行研究,实验表明,该方法在保证最优近似率的同时,大幅降低了计算成本。
Nov, 2017
本研究以连续贪心算法为基础,研究了具有一般性骨架约束的随机子模最大化问题,主要应用于在线学习,团队形成,设施位置,影响最大化,主动学习和感知目标函数。实验表明,使用多项式梯度估计代替样本估计,可有效减少随机性并缩短执行时间。
Mar, 2023
本文提出自适应子模性的概念,将子模集函数推广到自适应策略,并使用自适应贪心算法解决具有不确定性结果的随机优化问题,通过使用懒惰评估方法显著加快了算法。通过提供子模目标的几个示例,包括传感器放置,病毒营销和主动学习,证明了自适应子模性的实用性。
Mar, 2010
本文提出了鲁棒次模函数最大化及其在结构组合约束下的有效算法,旨在提高对次模优化的建模范围,尤其应用于单个或多个基序,背包以及具有分散鲁棒性的标准约束条件,该算法适用于离线和在线设置,并且在线问题的双标准解决方案具有 sub-linear 的遗憾。
Oct, 2017