Monge Property

释义 Definition

Monge 性质（Monge property）指一种常见于矩阵/代价函数中的“交叉不等式”结构：对矩阵 \(A\) 的任意 \(i \[ A_{i j}+A_{k \ell}\ \le\ A_{i \ell}+A_{k j}. \] 满足该性质的矩阵常称为 Monge array（Monge 矩阵）。它在动态规划、运输/分配问题、最短路与某些优化算法中很重要，因为能带来更快的算法（例如利用单调性/分治优化）。

发音 Pronunciation (IPA)

/ˈmɒnʒ ˈprɒpərti/

例句 Examples

The cost matrix satisfies the Monge property.
这个成本矩阵满足 Monge 性质。

Because the distance table has the Monge property, we can speed up the dynamic programming using divide-and-conquer optimization.
由于距离表具有 Monge 性质，我们可以用分治优化来加速动态规划。

词源 Etymology

Monge 来自法国数学家 Gaspard Monge（加斯帕尔·蒙日）的姓氏。许多以他命名的数学概念（如 Monge 阵、Monge-Ampère 方程）都与几何、优化与偏微分方程等领域相关；“Monge property”在算法与组合优化中用于描述一种有利的代价结构。

相关词 Related Words

• Monge Array
• Totally Monotone
• Quadrangle Inequality
• Divide-And-Conquer DP
• Dynamic Programming
• Transportation Problem
• Assignment Problem
• Convexity

文学与著作 Literary Works

• Algorithm Design（Jon Kleinberg, Éva Tardos）——在算法设计语境中讨论 Monge 数组/相关优化技巧。
• Combinatorial Optimization: Polyhedra and Efficiency（Alexander Schrijver）——组合优化中涉及 Monge 结构与相关问题。
• Integer and Combinatorial Optimization（George L. Nemhauser, Laurence A. Wolsey）——优化与整数规划背景下提及具有特殊结构的代价矩阵（含 Monge 类）。
• The Monge–Ampère Equation（Cédric Villani 等相关著作/讲义体系）——虽侧重 PDE，但展示“Monge”命名传统与数学脉络。