May, 2023

超模秩：集函数分解与优化

PDF
TL;DR介绍了一个新的概念：在格子上定义函数的超模秩，是把函数分解为超模函数之和所需的最小项数；并且通过对不同偏序关系下定义超模和的方式，描述了具有固定超模秩的函数，以及类似地定义亚模秩；使用亚模分解来优化集合函数用于解决单调集合函数最大化和集合函数比率最小化的问题，特别地使用亚模秩的一个上界将优化问题分解成亚模子问题，从而提高了近似比的保证。
发现论文，激发创造
  • 子模函数：扩展、分布和算法。一份调查

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

    Dec, 2009

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

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

    Oct, 2010

  • 二次可分解次模函数最小化

    本文提出了一种新的凸优化问题 —— 二次可分解子模函数极小化问题，该问题与可分解子模函数极小化问题密切相关，并在许多基于图和超图的学习环境中产生，例如基于图的半监督学习和 PageRank。我们采用了一种新的解决策略，并描述了可以通过随机坐标下降（RCD）方法和锥体投影优化的目标。我们还确定了 RCD 算法的线性收敛率，并开发了具有可证明性能保证的高效投影算法。基于超图的半监督学习的数字实验证实了所提出算法的效率，并证明了与现有最先进方法相比，在预测精度方面取得了显着的改进。

    Jun, 2018

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

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

    Jun, 2014

  • 子模函数近似

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

    Apr, 2013

  • 在联邦环境中的可分解子模函数最大化

    提出了一种联邦优化设置的分解可分模函数的优化方法，使用连续贪婪算法在客户端和中央服务器之间进行并行小步骤的局部优化，通过抽样和定期聚合来减少通信成本，并展示了如何与最大覆盖和设施位置等离散分解模最优化问题相结合。

    Jan, 2024

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

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

    May, 2008

  • 快速最大化整数晶格上的非次模、单调函数

    该论文提出了两种多项式查询复杂度的逼近算法来最大化整数格上的非子模函数，同时提出了一个广义影响力最大化框架来推广之前的研究，并在此背景下展示了我们算法的高效性。

    May, 2018

  • 通过多线性松弛和竞争解决方案的子模函数最大化

    研究了如何在不同的 packing 类型约束下，最大化定义在给定集合上的非负子模函数，提出了一个基于多线性扩展和分数解取整的算法框架，并且解决了其中的一些重要限制问题，开辟了线性和子模函数最大化的新方法。

    May, 2011

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

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

    Jul, 2023