Submodularity

Definition / 定义

Submodularity（次模性）：一种集合函数（或离散函数）的性质，核心直觉是“边际收益递减”——当你已经拥有的集合越大，再加入同一个元素所带来的增益通常越小。它常用于组合优化、机器学习中的特征选择、信息检索与资源分配等问题。
（注：在更严格的数学表述中，它对应某类“离散的凹性/凸性对偶”结构；此外在不同领域也会有等价定义。）

Pronunciation / 发音

/ˌsʌbˌmɑːdjʊˈlærɪti/

Examples / 例句

Submodularity often captures the idea of diminishing returns in set selection.
次模性常用来刻画集合选择中的“边际收益递减”。

Because the objective has submodularity, a greedy algorithm can achieve a strong approximation guarantee.
由于目标函数具有次模性，贪心算法通常能得到较强的近似保证。

Etymology / 词源

submodularity 来自 **sub-**（“次/亚/在…之下”）+ modular（与 modulus “模/模数/尺度”相关）+ -ity（名词后缀，表示性质）。在数学语境中，modular 关联到“模性（modularity）”这种更强的结构；submodularity 字面上可理解为“低于/弱于模性的性质”，即一种比“模性”更一般、更宽松的条件。

Related Words / 相关词

• Submodular
• Modularity
• Supermodularity
• Diminishing
• Marginal
• Greedy
• Optimization
• Set

Literary Works / 文学与著作示例

• Submodular Functions and Optimization（Satoru Fujishige）：以次模函数/次模性为核心主题的经典专著。
• Combinatorial Optimization: Polyhedra and Efficiency（Alexander Schrijver）：组合优化权威著作中多处涉及次模结构与相关理论。
• Approximation Algorithms（Vijay V. Vazirani）：在近似算法背景下讨论与次模性相关的优化问题与保证。
• The Nature of Mathematical Modeling（Neil Gershenfeld）等应用建模类书籍中，也可能在离散优化/信息增益语境下提及次模思想（通常以“diminishing returns”的形式出现）。