快速最大化整数晶格上的非次模、单调函数
本研究提出了一种新的算法,用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解,其近似保证是 0.372,这是在 1/e 近似之上的首次改进,由连续贪心算法 [Feldman 等,FOCS2011] 实现。
Aug, 2016
本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化,同时满足多个基数约束或背包约束,特别是在 k 个划分拟阵约束下,改进了以前已知的最佳保证,获得了(1 /k+1 + 1 /k-1 + ε)的近似保证。
Feb, 2009
研究了如何在不同的 packing 类型约束下,最大化定义在给定集合上的非负子模函数,提出了一个基于多线性扩展和分数解取整的算法框架,并且解决了其中的一些重要限制问题,开辟了线性和子模函数最大化的新方法。
May, 2011
研究了 Greedy 算法在非子模不减集函数基数约束最大化中的性能,并证明了在一些重要的非子模函数如贝叶斯 A - 最优目标函数中,该算法具有很强的经验性能。我们以广义曲率 α 和子模性比率 γ 的组合为特点,证明了其理论保证,特别地,对于基数约束最大化,我们证明了 Greedy 算法具有紧密的近似保证为 1/α(1-e^(-γα))。另外,我们还限制了在几个重要的真实世界目标中子模性比率和曲率,包括贝叶斯 A - 最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。
Mar, 2017
本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题,建立了离散问题和连续松弛之间的强联系,并利用这种联系提出了近似算法和确定性技术,得到了很好的解决方案。
Jan, 2011
本文介绍了一种弱 DR 属性,用于给出有关子模性的统一特征,证明了可以在近似保证的同时高效地最大化子模连续函数,为在一般下闭凸约束条件下最大化单调 DR - 子模连续函数和在盒约束条件下的非单调子模连续函数提供了算法,并探讨了其在不同实际应用中的应用性。
Jun, 2016
提出一种基于模拟退火的新算法用于解决子模块最大化问题,证明该算法支持两种问题的改进近似,在数值预言模型中,子模块最大化问题在独立约束和基约束条件下都不可能有更好的解决方案。
Jul, 2010
我们通过降低一个非单调子模函数的约束条件 k 到同样约束条件 k 下最大化一个单调子模函数,肯定回答了陈和彭提出的问题,并得到了第一个动态算法来解决非单调子模函数最大化问题。我们的算法保持了一个 (8+ε) 近似的解,并且每次更新使用预期平摊的 O (ε^-3 * k^3 * log^3 (n) * log (k)) 或者 O (ε^-1 * k^2 * log^3 (k)) 的预言查询。此外,我们展示了我们的动态算法在视频概述和基于几个真实数据集的最大割问题上的优势。
Nov, 2023
本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了 5.83 近似和 O (nlogn) 时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。
Jul, 2020