ICMLAug, 2022

基于单调性不稳定的麦特罗伊德上的非单调子模最大化

PDF
TL;DR该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题，在此问题中，目标是提取一个小型数据集的摘要，即使在对手删除一些元素后也包含高价值独立集，该研究提供了具有常数因子逼近比的近似算法，其中空间复杂度取决于拟阵的秩 k 和已删除元素的数量 d。
发现论文，激发创造
  • 基于拟阵的删除鲁棒子模型最大化

    本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。

    Jan, 2022

  • 基于拟阵的全动态次模最大化

    研究单调子模函数下的最大值问题以及约束条件下的问题，提出了一个随机的动态算法，并给出了一个高效的数据结构来处理发生了添加和删除变化的值，该算法能够提供一个 4 近似解。

    May, 2023

  • 基于拟阵约束的 k 次次模最大化的快速算法

    应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数，提出逼近算法来最大化满足单调和非单调 k - 次模函数，并提供了关于时间复杂度的结果，同时还介绍了针对总大小约束的快速算法。

    Jul, 2023

  • 满足拟阵和背包约束的非单调次模最大化

    本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化，同时满足多个基数约束或背包约束，特别是在 k 个划分拟阵约束下，改进了以前已知的最佳保证，获得了（1 /k+1 + 1 /k-1 + ε）的近似保证。

    Feb, 2009

  • 基于动态规划的拟阵子模最大化算法

    针对子模最大化问题，本文提出了一种动态算法，该算法对于给定序列的插入和删除操作，维护了一个在任一时间点上具有 4+ε 近似度的子系统，其参数化为 matroid 约束的秩 k，并且查找复杂度与序列长度无关；同时，我们还探讨了基于基数约束的子模最大化问题的动态算法。

    Jun, 2023

  • 大规模下具有删除鲁棒性的子模最大化

    本文主要研究如何在保护用户隐私和确保公平性的同时，高效地从大型用户生成的数据集中提取有用信息。该问题被描述成删除鲁棒子模型最大化的一个实例，我们提出了第一种内存高效的集中式、流式和分布式方法，对任意数量的敌对删除具有常数逼近保证。我们对我们的算法在真实世界的应用进行了广泛评估，包括：（i）具有位置隐私限制的 Uber 接送点；（ii）收入预测和犯罪率预测的公平性限制的特征选择；以及 (iii) 由 2,458,285 个特征向量组成的人口普查数据的删除汇总结果的健壮性。

    Nov, 2017

  • 非子模目标强鲁棒性最大化

    研究了在最劣情况下，基于一个基数约束 k 最大化单调集合函数的删除问题，提出了一种新的算法 Oblivious-Greedy，并对于更广泛的非凸优化问题证明了首个常数因子逼近保证，通过提出新的度量参数，如逆曲率，证明了这些结果适用于线性区域，并通过支撑选择和方差缩小等两个实际问题的案例研究得到了验证。

    Feb, 2018

  • 并行下考虑拟阵约束和装箱限制的子模块最大化

    本文提出了一种在单个 matroid 约束或多个 packing 约束下，通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法，该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例，并且在自适应轮次和并行运行时间上提出了指数级别的加速。

    Aug, 2018

  • 子模最大化问题的紧凑组合算法在矩阵约束条件下的应用

    提出了一种基于组合数学的算法，用于求解在一个制约性匹配中的单调子模优化问题，算法具有很高的精度和时间效率。

    Apr, 2012

  • 约束次模优化问题的全动态算法

    本研究在完全动态的环境下，旨在最大化基数约束下的单调子模函数，研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法，并结合经验研究证明了算法性能的优越性。

    Jun, 2020