We define the supermodular rank of a function on a lattice. This is the smallest number of terms needed to decompose it into a sum of supermodular functions. The supermodular summands are defined with respect to different partial orders. We characterize the maximum possible value of the supermodular rank and describe the functions with fixed supermodular rank. We analogously define the submodular rank. We use submodular decompositions to optimize set functions. Given a bound on the submodular rank of a set function, we formulate an algorithm that splits an optimization problem into submodular subproblems. We show that this method improves the approximation ratio guarantees of several algorithms for monotone set function maximization and ratio of set functions minimization, at a computation overhead that depends on the submodular rank.

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

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