小批量次模最大化
本研究提出了一种新的算法,用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解,其近似保证是 0.372,这是在 1/e 近似之上的首次改进,由连续贪心算法 [Feldman 等,FOCS2011] 实现。
Aug, 2016
本文研究了带有子模性目标函数的组合优化问题,提出了一种基于新技术的算法来优化多线性松弛问题,该算法避免了对称性等性质的需要,适用于约束问题,相比之前的算法,它具有更好的保证。
Nov, 2016
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了 5.83 近似和 O (nlogn) 时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。
Jul, 2020
本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化,同时满足多个基数约束或背包约束,特别是在 k 个划分拟阵约束下,改进了以前已知的最佳保证,获得了(1 /k+1 + 1 /k-1 + ε)的近似保证。
Feb, 2009
提出一种基于模拟退火的新算法用于解决子模块最大化问题,证明该算法支持两种问题的改进近似,在数值预言模型中,子模块最大化问题在独立约束和基约束条件下都不可能有更好的解决方案。
Jul, 2010
研究论文中,我们探讨了序列次模优化的基本问题,针对从一个给定集合中选择和排序 k 个项目的场景,最大化 k 个(可能非单调的)次模函数的加权求和,其中每个函数 f_j 将序列中的前 j 个项目作为输入。不同于过去关于单调情形的研究,本文首次考虑了具有非单调次模函数的问题,并提出了对于灵活和固定长度约束以及具有相同效用函数的特殊情况的有效解决方案。通过视频推荐领域的实证评估,我们提出的算法的有效性得到了验证。这项研究的结果对推荐系统和组合优化等多个领域具有重要意义,其中项目的排序对于整体价值具有显著影响。
Aug, 2023
通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的 MapReduce 循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015