May, 2008

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

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

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

    Apr, 2013

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

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

    May, 2019

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

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

    Dec, 2009

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

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

    Nov, 2013

  • 分布式基于配对次模函数的大于内存子集选择

    通过提出一种新颖的分布式界限算法，并使用多轮基于分区的分布式贪心算法，此论文解决了子集选择问题，能够在没有或极小损失质量的情况下，找到高质量的子集。

    Feb, 2024

  • 子模函数学习：凸优化观点

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

    Nov, 2011

  • 具有近似最优的适应性和查询复杂度的子模最大化

    本文研究自适应子模型优化的适应性和查询复杂度，提出了适用于最大基数约束的单调子模型函数的分布式算法，并将其推广到子模型覆盖问题。

    Jul, 2018

  • 近似最小化次模函数差的算法及应用

    本研究扩展了 Narasimhan 和 Bilmes 的工作，提出了基于子模函数差别最小化的新算法，该算法能有效地解决多种组合约束的问题，并且能够用于许多机器学习问题中，它在性能上优于现有的算法。

    Jul, 2012

  • 学习和最小化子模函数的曲率和最优算法

    本文探究了三个相关且重要的机器学习问题。我们展示了这三个问题的复杂度都依赖于子模函数的 ' 曲率 '，并提供了改进旧有结果的上下界。我们证明了曲率对于子模函数的近似、最小化和学习有影响，并通过实验结果支持了我们的理论结论。

    Nov, 2013

  • 子模最大化问题的对称性和可近似性

    研究了使用问题的多线性松弛的优化问题的一些最近结果，提出了一种与对称差相关的不可近似性结果的一般方法，证明了最大化基于 matroid 的非负次模函数问题不存在常数近似算法。

    Oct, 2011