流式自适应次模最大化
本文提出了第一个高效的单遍流式计算算法 Streaming Local Search,用于在独立系统和多重背包约束下,同时最大化非单调子模函数,解决实时提取和总结大规模视频流的问题。
Jun, 2017
该论文提出了首个一次遍历的流算法,用于求解子模最大化问题,采用数据采样,能够在各种情况下获得最紧密的逼近保证,同时具有最小的内存占用和对函数评估数量的最低要求,试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上
Feb, 2018
该研究主要针对单次流式处理的情况下,最大化一个非负子模集函数 f 编制一些确定性和随机算法,以实现对 p 匹配约束条件的大约 1 /p 的逼近,假设具有时间和资源约束。
Apr, 2015
本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题,并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。
Oct, 2020
研究论文中,我们探讨了序列次模优化的基本问题,针对从一个给定集合中选择和排序 k 个项目的场景,最大化 k 个(可能非单调的)次模函数的加权求和,其中每个函数 f_j 将序列中的前 j 个项目作为输入。不同于过去关于单调情形的研究,本文首次考虑了具有非单调次模函数的问题,并提出了对于灵活和固定长度约束以及具有相同效用函数的特殊情况的有效解决方案。通过视频推荐领域的实证评估,我们提出的算法的有效性得到了验证。这项研究的结果对推荐系统和组合优化等多个领域具有重要意义,其中项目的排序对于整体价值具有显著影响。
Aug, 2023
本文提出了单遍流式和在线算法的受约束 k - 次模最大化,其中包含基数和背包约束限制,该算法可以提供不错的近似解和高效的解决方案,并在广告分配等应用实例上得到了验证。
May, 2023
在具有一致性约束的动态环境中,我们研究了在基数约束下最大化单调次模函数,其在数据挖掘和机器学习中有多个应用。我们提供了在此场景中具有一致性和逼近质量之间不同权衡的算法。实验证明我们算法在真实世界实例中的有效性。
May, 2024
本文研究基于在线变体的子模函数最大化问题,探讨了两种特殊情况并得出了竞争比的上下界。具体而言,设计了一个 $1/e$ 竞争算法和一个针对最多只包含 k 个元素的解的常数竞争比算法。
Jan, 2015
本文研究在流式场景下,求解具有基数限制 k 的单调子模函数最大化问题,提出了一种基于 STAR-T 算法的新型分区结构和指数递减阈值规则,这种算法只需要一次遍历数据,即可保留简短而健壮的总结性概括,还证明了在删除汇总得到的任何 m 个元素后,基于剩余的元素运行的一种简单贪心算法 STAR-T-GREEDY 可获得近似,最后通过两项不同的数据汇总任务证明了 STAR-T 的性能媲美先前的贪心和流式方法。
Nov, 2017