Monge Problem

释义 / Definition

Monge 问题：指一类具有Monge 性质（Monge property）的优化问题，通常表现为其成本矩阵/距离矩阵满足特定的不等式结构（Monge 数组）。这种结构会使一些经典问题（如运输问题、分配问题、某些动态规划）可以用更快的专门算法求解。

常见的 Monge 性质表述之一（对矩阵 \(A\)）：对任意 \(i \[ A_{i,j}+A_{k,l}\le A_{i,l}+A_{k,j}. \]
（不同语境下也可能出现等价或变体形式。）

发音 / Pronunciation (IPA)

/mɒnʒ ˈprɒbləm/ (BrE)
/mɑːnʒ ˈprɑːbləm/ (AmE)

例句 / Examples

A Monge problem can often be solved faster than a general case.
Monge 问题通常比一般情形能更快求解。

Because the cost matrix satisfies the Monge property, the assignment problem admits a more efficient algorithm than the standard approach.
由于成本矩阵满足 Monge 性质，这个分配问题可以用比标准方法更高效的算法来解决。

词源 / Etymology

“Monge”来自法国数学家加斯帕尔·蒙日（Gaspard Monge, 1746–1818）的姓氏。以他名字命名的 Monge 数组/Monge 性质在运筹学与组合优化中非常重要：当问题的代价结构呈现这种“可交换更优”的规律时，就能利用结构性显著降低计算复杂度。

相关词 / Related Words

• Monge Array
• Monge Property
• Transportation Problem
• Assignment Problem
• Optimal Transport
• Cost Matrix
• Dynamic Programming
• SMAWK Algorithm

作品举例 / Notable Works

• Gaspard Monge, “Mémoire sur la théorie des déblais et des remblais” (1781)（与最优运输思想相关的经典来源之一）
• R. Burkard, M. Dell’Amico, S. Martello, Assignment Problems（讨论分配问题及相关结构，常涉及 Monge 情形）
• A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency（组合优化权威教材，包含结构化矩阵/特殊可解情形的相关讨论）
• R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows（网络流与运输类问题教材，常提到可利用特殊代价结构加速的情形）