- 子模集约束下的公平性最大化
在机器学习中,基于 matroid 约束的子模最大化是一个具有各种应用的基本问题。最近,已经在有限制条件下的流式和离线设置下考虑了基于基数约束的子模最大化中的公平性,但对于更一般的 matroid 约束问题,只有在流式设置下且只考虑单调目标 - 基于拟阵约束的 k 次次模最大化的快速算法
应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数,提出逼近算法来最大化满足单调和非单调 k - 次模函数,并提供了关于时间复杂度的结果,同时还介绍了针对总大小约束的快速算法。
- 基于动态规划的拟阵子模最大化算法
针对子模最大化问题,本文提出了一种动态算法,该算法对于给定序列的插入和删除操作,维护了一个在任一时间点上具有 4+ε 近似度的子系统,其参数化为 matroid 约束的秩 k,并且查找复杂度与序列长度无关;同时,我们还探讨了基于基数约束的子 - ICML基于拟阵的全动态次模最大化
研究单调子模函数下的最大值问题以及约束条件下的问题,提出了一个随机的动态算法,并给出了一个高效的数据结构来处理发生了添加和删除变化的值,该算法能够提供一个 4 近似解。
- ICML在 Matroid 约束下流式子模最大化中的公平性
论文研究流式子模最大化算法中公平性的应用,提出了针对劣模最大化算法的公平机器学习算法,包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后,通过社会网络中的最大覆盖,电影推荐和样本聚类等应用的实验验证了其有效性。
- 决策、反事实解释与战略行为
本文旨在在战略环境下寻找最优的政策和对策解释,包括 NP 难的问题,非降性和子模性,用标准贪心算法获得近似保证。最后,我们表明通过将拟阵约束加入问题的制定中,我们可以提高对策解释的最优集合的多样性,并激励整个人口谱上的个体自我改进。
- 并行下考虑拟阵约束和装箱限制的子模块最大化
本文提出了一种在单个 matroid 约束或多个 packing 约束下,通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法,该算法在 submodular maximization with a matroid - 基于条件梯度方法的随机次模最大化:弥合差距
研究连续子模最大化问题,通过提供新颖的算法并使用随机持续优化作为接口,在满足约束条件的情况下获得了紧密的逼近保证。
- 在线自由处理子模最大化:随机化对分割矩阵 0.25 优势
本文研究了带有破坏性(free disposal)的 matroid 约束下的在线次模最大化问题。针对 k-uniform matroids,本文提出了一个与以往最优算法竞争比例更高的确定性算法;同时,本文也探讨了在 partition m - 在线玄学最大化下的基合约束与学习分配应用
本文提出了一种能够动态地为信息源进行排序,同时又能保证重复信息的减少不会影响子模函数的最优化问题算法,并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。
- 受限曲率下次模优化和超模优化的最优逼近
论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题,特别地,当目标函数有闭合总曲率时,获得了一个 (1-c/e)- 近似的结果;该算法基于连续贪心算法和非随机局部搜索的修改,并进行了扩展以包括在一些特定场景下的应用,例 - 曲率约束下的子模函数
本论文探究了在具有字符串子模性的目标函数中如何客观地选择一系列行动以优化目标函数的问题,并通过引入曲率限制(如总向后曲率、总向前曲率和元前向曲率)来提高近似度,并研究了具有曲率约束的字符串子模函数的应用。
- 子模最大化问题的紧凑组合算法在矩阵约束条件下的应用
提出了一种基于组合数学的算法,用于求解在一个制约性匹配中的单调子模优化问题,算法具有很高的精度和时间效率。
- 最大和差异化,单调子模函数和动态更新
研究了一类问题,该问题的距离是一个度量,约束是一个 matroid 中的独立性,质量则由单调子模函数确定,多样性定义为 S 中物体之间的距离之和,提出了两种算法:基于基数约束的贪心算法和基于任意 matroid 约束的局部搜索算法,并证明了 - 模拟退火算法进行子模最大化
提出一种基于模拟退火的新算法用于解决子模块最大化问题,证明该算法支持两种问题的改进近似,在数值预言模型中,子模块最大化问题在独立约束和基约束条件下都不可能有更好的解决方案。