模模块极值相遇流式计算:匹配,拟阵等
该研究主要针对单次流式处理的情况下,最大化一个非负子模集函数 f 编制一些确定性和随机算法,以实现对 p 匹配约束条件的大约 1 /p 的逼近,假设具有时间和资源约束。
Apr, 2015
该论文提出了首个一次遍历的流算法,用于求解子模最大化问题,采用数据采样,能够在各种情况下获得最紧密的逼近保证,同时具有最小的内存占用和对函数评估数量的最低要求,试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上
Feb, 2018
本文提出了第一个高效的单遍流式计算算法 Streaming Local Search,用于在独立系统和多重背包约束下,同时最大化非单调子模函数,解决实时提取和总结大规模视频流的问题。
Jun, 2017
论文研究流式子模最大化算法中公平性的应用,提出了针对劣模最大化算法的公平机器学习算法,包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后,通过社会网络中的最大覆盖,电影推荐和样本聚类等应用的实验验证了其有效性。
May, 2023
在具有一致性约束的动态环境中,我们研究了在基数约束下最大化单调次模函数,其在数据挖掘和机器学习中有多个应用。我们提供了在此场景中具有一致性和逼近质量之间不同权衡的算法。实验证明我们算法在真实世界实例中的有效性。
May, 2024
本文在数据流的上下文中,提供了一种基于滑动窗口模型的次模优化的近似算法,该算法维护了一个解决方案,考虑的仅是最后 $W$ 个元素,使用空间多项式对元素值的传播速度的对数级别,线性大小的解决方案,并保持高品质的解,实际表现远超理论界限。
Oct, 2016
该研究研究了二遍流算法在最大二分匹配上的应用,提出了结合子抽样和贪心匹配算法以及度有界半匹配算法的元算法,证明了近似算法的下限,并且发现了最优算法,同时也强调了需求使用新技术以进一步改进。
Jul, 2021
针对子模最大化问题,本文提出了一种动态算法,该算法对于给定序列的插入和删除操作,维护了一个在任一时间点上具有 4+ε 近似度的子系统,其参数化为 matroid 约束的秩 k,并且查找复杂度与序列长度无关;同时,我们还探讨了基于基数约束的子模最大化问题的动态算法。
Jun, 2023
本文提出了一种在单个 matroid 约束或多个 packing 约束下,通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法,该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例,并且在自适应轮次和并行运行时间上提出了指数级别的加速。
Aug, 2018
本文介绍了在线子模二分图匹配问题(Online Submodular Bipartite Matching)的概念和算法,该问题旨在在考虑到多样性和相关性的情况下,通过优化子模函数 $f$ 来匹配边的集合以得到最佳匹配。
Nov, 2018