子模最大化问题的紧凑组合算法在矩阵约束条件下的应用
本文提出了一种在单个 matroid 约束或多个 packing 约束下,通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法,该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例,并且在自适应轮次和并行运行时间上提出了指数级别的加速。
Aug, 2018
应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数,提出逼近算法来最大化满足单调和非单调 k - 次模函数,并提供了关于时间复杂度的结果,同时还介绍了针对总大小约束的快速算法。
Jul, 2023
本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化,同时满足多个基数约束或背包约束,特别是在 k 个划分拟阵约束下,改进了以前已知的最佳保证,获得了(1 /k+1 + 1 /k-1 + ε)的近似保证。
Feb, 2009
论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题,特别地,当目标函数有闭合总曲率时,获得了一个 (1-c/e)- 近似的结果;该算法基于连续贪心算法和非随机局部搜索的修改,并进行了扩展以包括在一些特定场景下的应用,例如最大熵抽样和列子集选择问题。
Nov, 2013
提出一种基于模拟退火的新算法用于解决子模块最大化问题,证明该算法支持两种问题的改进近似,在数值预言模型中,子模块最大化问题在独立约束和基约束条件下都不可能有更好的解决方案。
Jul, 2010
针对子模最大化问题,本文提出了一种动态算法,该算法对于给定序列的插入和删除操作,维护了一个在任一时间点上具有 4+ε 近似度的子系统,其参数化为 matroid 约束的秩 k,并且查找复杂度与序列长度无关;同时,我们还探讨了基于基数约束的子模最大化问题的动态算法。
Jun, 2023
本文研究了带有破坏性(free disposal)的 matroid 约束下的在线次模最大化问题。针对 k-uniform matroids,本文提出了一个与以往最优算法竞争比例更高的确定性算法;同时,本文也探讨了在 partition matroids 约束下确定性算法的下限,及随机算法的优势。
Oct, 2016
本文提出了一种能够动态地为信息源进行排序,同时又能保证重复信息的减少不会影响子模函数的最优化问题算法,并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。
Jul, 2014
研究了具有健壮性约束的基数约束单调次模函数最大化问题,提出了逼近算法,并在限制相对较小的情况下,得到了相对较好的逼近结果,并应用结果解决了更普遍的独立性约束下的最大化问题。
Jul, 2015