提出了一种基于组合数学的算法,用于求解在一个制约性匹配中的单调子模优化问题,算法具有很高的精度和时间效率。
Apr, 2012
针对拥有大规模实例的问题,本文提出了第一个自适应复杂度为 O (log n),且求解非单调子模问题的背包约束问题的常数因子逼近算法,该算法提出了一个子线性适应性的组合方法,其查询值仅为 O (n)。
Feb, 2021
非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近
Aug, 2023
本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了 5.83 近似和 O (nlogn) 时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。
Jul, 2020
提出一种基于模拟退火的新算法用于解决子模块最大化问题,证明该算法支持两种问题的改进近似,在数值预言模型中,子模块最大化问题在独立约束和基约束条件下都不可能有更好的解决方案。
Jul, 2010
本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化,同时满足多个基数约束或背包约束,特别是在 k 个划分拟阵约束下,改进了以前已知的最佳保证,获得了(1 /k+1 + 1 /k-1 + ε)的近似保证。
Feb, 2009
我们提出了一种新的算法,可以在实践中有效地解决非单调受限子模型最大化问题,结合了 0.385 的逼近保证和低的查询复杂度。通过在各种机器学习应用中进行实验,包括电影推荐、图像摘要等,我们评估了我们算法的实验性能,证明了我们方法的功效。
May, 2024
本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题,建立了离散问题和连续松弛之间的强联系,并利用这种联系提出了近似算法和确定性技术,得到了很好的解决方案。
Jan, 2011
本文探讨了子模最大化算法的适应性,证明了一个新的算法可以在 O (log n) 自适应回合内实现接近于最优 1-1/e 近似。
Apr, 2018
本文提出了一种在单个 matroid 约束或多个 packing 约束下,通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法,该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例,并且在自适应轮次和并行运行时间上提出了指数级别的加速。
Aug, 2018