假设我们得到一个方阵A。我们的目标是通过行排列最大化最小的对角线元素。换句话说，对于给定的矩阵 A，我们有 n 个对角线元素，因此我们有最小 $min{d_i}$。我们的目的是通过行排列达到可能具有最大最小对角线元素的矩阵。
这就像在所有行排列上$max min{d_i}$。
例如，假设 A = [4 3 2 1; 1 4 3 2; 2 1 4 3; 2.5 3.5 4.5 1.5]。对角线是 [4， 4， 4， 1.5]。对角线的最小值为 1.5。我们可以交换第 3 行和第 4 行以获得新矩阵 \tilde_A = [4 3 2 1; 1 4 3 2; 2.5 3.5 4.5 1.5; 2 1 4 3]。新的对角线是 [4， 4， 4.5， 3]，新的最小值为 3。从理论上讲，这是我能得到的最好的结果，因为似乎没有更好的选择：3 似乎是最大最小值{d_i}。
在我的问题中，n 要大得多，比如 1000。我知道有n！行排列，所以我无法在理论上通过每个排列。我知道贪婪的算法会有所帮助——我们从第一行开始。如果a_11不是第一列中最小的，我们将a_11与第一列中最大的元素交换逐行排列。然后，我们将a_22与第二列中的所有剩余元素（a_12除外）进行比较来查看第二行。如果不是最小的，请交换a_22。... ...等。我们一直这样做，直到最后一行。
有没有更好的算法来做到这一点？
这类似于最小欧几里得匹配，但它们并不相同。
假设您想知道是否有比 3 更好的问题解决方案。
将矩阵更改为严格大于 3 的每个元素都有一个 1：
4 3 2 1 1 0 0 0
1 4 3 2 0 1 0 0
2.5 3.5 4.5 1.5 -> 0 1 1 0
2 1 4 3 0 0 1 0
您的问题可以解释为试图在二分图中找到完美匹配，该二分图将此二进制矩阵作为其二邻关系图。
在这种情况下，很容易看出无法改善结果，因为无法对行重新排序以使最后一列中的对角线条目大于 3。
对于较大的矩阵，有有效的算法来确定二分图中的最大匹配。
这提出了一种算法：
- 使用平分法查找生成的图形具有完美匹配的最大值
- 与最大值完美匹配对应的赋值将等于行的最佳排列
编辑
此 Python 代码说明了如何使用 networkx 库来确定图形是否与特定截止值完美匹配。
import networkx as nx
A = [[4,3,2,1],
[1,4,3,2],
[2,1,4,3],
[2.5,3.5,4.5,1.5]]
cutoff = 3
G=nx.DiGraph()
for i,row in enumerate(A):
G.add_edge('start','row'+str(i),capacity=1.0)
G.add_edge('col'+str(i),'end',capacity=1.0)
for j,e in enumerate(row):
if e>cutoff:
G.add_edge('row'+str(i),'col'+str(j),capacity=1.0)
if nx.max_flow(G,'start','end')<len(A):
print 'No perfect matching'
else:
print 'Has a perfect matching'
*1000 的随机矩阵，在我的计算机上大约需要 1 秒。
如果将行 i 移动到行 j 且为零，则设 $x_{ij}$ 为 1。
您对以下整数程序感兴趣：
最大 Z
\sum_{i=0}^n x_{ij} = 1 \forall j
\sum_{j=0}^n x_{ij} = 1 \forall i
A[j，j]x_{ij}>= z
然后将其插入 GLPK、Gurobi 或 CPLEX。或者，使用自己的分支和绑定求解来求解 IP。