NIPSNov, 2013

带有子模块覆盖和子模块背包约束的子模块优化

PDF
TL;DR本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数（子模覆盖）和在满足子模上限的约束条件下最大化子模函数（子模背包）。我们将这些问题表述为约束优化问题，并获得许多有界逼近保证。此外，我们证明了这两个问题的紧密关联，并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后，我们通过实验证明了本文算法的效果和良好的可扩展性。
发现论文，激发创造
  • 子模函数学习：凸优化观点

    本文从凸分析的角度介绍了子模函数，论述了子模函数最小化与各类凸优化问题的关系，提出了新的高效算法以及多种子模函数在机器学习中的应用。

    Nov, 2011

  • 子模近似：基于采样的算法与下界

    本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广，包括子模型负载平衡，子模型最稀疏切割和子模型平衡切割等，并建立了这些问题的近似界限。

    May, 2008

  • 子模函数：扩展、分布和算法。一份调查

    本文介绍了子模函数的连续松弛及其在优化问题中的应用，同时提出了一种基于对称子模函数的基数约束下，最小化函数的常系数逼近算法。

    Dec, 2009

  • 非子模无约束最小化的最优逼近

    该论文介绍了如何将亚模模函数最小化算法扩展到近似最小化非亚模函数并给出了理论保证。

    May, 2019

  • 具背包约束的单调和非单调次模最大化的近似算法

    本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题，建立了离散问题和连续松弛之间的强联系，并利用这种联系提出了近似算法和确定性技术，得到了很好的解决方案。

    Jan, 2011

  • 随机子模极大化：覆盖函数的情形

    该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化，通过将扩展线性化处理并通过向上投影处理，得到离散解，针对加权覆盖函数进行研究，实验表明，该方法在保证最优近似率的同时，大幅降低了计算成本。

    Nov, 2017

  • 子模函数近似

    本文研究了 submodular functions 可以被其他简单类别的 submodular functions 逼近的程度和方法，并证明了一些上下界。

    Apr, 2013

  • 概率约束次模函数的优化

    研究使用机会约束的子模型优化问题，探讨贪心算法在应用对 Chernoff 边界进行约束违规估计的替代函数后，能高效地获得高品质解，同时在社交网络问题中也能保持有效性。

    Nov, 2019

  • 优化具有变量不确定性的概率约束子模问题

    本文研究了确定性设定中的概率约束子模优化问题，提出了一种新的分析方法，并提供了贪心算法来近似求解最优解。在实验中，演示了算法在几个最大覆盖问题和影响力最大化问题上的有效性。

    Sep, 2023

  • 针对背包约束的快速自适应非单调子模型最大化

    本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法，该算法实现了 5.83 近似和 O (nlogn) 时间复杂度；并将其转移到随机版本的问题，得到了首个非单调目标的常数近似，实验表明该方法在实际和合成数据上的性能得到了改进。

    Jul, 2020