Nov, 2008

二元次模函数的表达能力

PDF
TL;DR通过分析具有值约束的表达能力以及函数的某些代数性质，我们否定了一个开放问题，即是否所有的布尔子模函数都可以分解成可能更大的一组变量上的二元子模函数之和，并确定了这种约束的一些限制。
boolean submodular functionsbinary submodular functionsvalued constraintsexpressibility reductionextreme rays
发现论文，激发创造
  • 子模函数近似

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

    Apr, 2013

  • 最小化 k - 次模函数

    本文研究了 k - 次模函数及其在离散函数中的应用，给出了 k - 次模多面体概念及 k - 次模函数的极小 - 极大定理，同时将以前次模函数的极小 - 极大定理推广到了 k - 次模函数的情形。

    Sep, 2013

  • 次模性、凸性和凹性的多面体方面

    本文通过扩展 Edmonds 和 Lovasz 的研究，提供了关于子模性与凸性和凹性之间关系的更完整的画面，同时探讨了子模最大化的优化条件和一些近似条件的应用。

    Jun, 2015

  • 可分解次模函数的高效最小化

    本文研究了一类新的子模函数优化问题，提出了一种基于平滑凸优化的算法 SLG，可用于解决具有数万个变量的分解子模函数问题，而且在一些合成基准测试和联合分类和分割任务中优于现有的子模函数优化算法。

    Oct, 2010

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

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

    May, 2008

  • 弱次模函数

    本文研究了弱次模函数的性质及优化问题，其中包括了一些次超模函数，并提出了在均匀和一般性拟阵约束下最大化弱次模函数的优化问题，在此问题中，我们证明了标准贪心算法和简单局部搜索算法的算法近似比分别为 5.95 和 10.22。

    Jan, 2014

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

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

    Dec, 2009

  • 可分解子模函数最小化的收敛速度

    本文介绍一种易用且可并行的用于最小化由 “简单” 子模函数组成的子模函数的算法，并在几何子模多面体的基础上，利用谱图理论结果证明该算法线性收敛，并给出了收敛速率的上下界。

    Jun, 2014

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

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

    Nov, 2011

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

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

    Nov, 2013