最大化矩阵的最小对角线元素的算法

Question

假设我们有一个方阵 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 似乎是最大值 min{d_i}.

在我的问题中，n 大于 1000。我知道有 n!行排列，所以我无法在理论上经历每个排列。我知道贪心算法会有所帮助——我们从第一行开始。如果 a_11 不是第一列中最小的，我们按行置换将 a_11 与第一列中的最大元素交换。然后我们通过将 a_22 与第二列中的所有剩余元素(a_12 除外)进行比较来查看第二行。如果 a_22 不是最小的，则交换它。 ......等等。我们一直这样做到最后一行。

有没有更好的算法来做到这一点？

这类似于最小欧几里德匹配，但它们并不相同。

Answer 1

假设您想知道是否有比 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

您的问题可以解释为试图在二分图中找到一个完美匹配，该二分图将此二进制矩阵作为其 biadjacency graph。 .

在这种情况下，很容易看出无法改进结果，因为无法重新排序行以使最后一列中的对角线条目大于 3。

对于更大的矩阵，有有效的算法来确定maximal matchings in bipartite graphs .

这提出了一种算法:

1. 使用二分法找到生成的图具有完美匹配的最大值
2. 与最大值完美匹配对应的分配将等于行的最佳排列

编辑

这段 Python 代码说明了如何使用 networkx library以确定图形是否具有特定截止值的完美匹配。

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*1000 的随机矩阵，在我的计算机上大约需要 1 秒。