Algorithm to maximize the smallest diagonal element of a matrix

Question

Suppose we are given a square matrix A. Our goal is to maximize the smallest diagonal element by row permutations. In other words, for the given matrix A, we have n diagonal elements and thus we have the minimum $min{d_i}$. Our purpose is to reach the matrix with possibly largest minimum diagonal element by row permutations.

This is like $max min{d_i}$ over all row permutations.

For example, suppose A = [4 3 2 1; 1 4 3 2; 2 1 4 3; 2.5 3.5 4.5 1.5]. The diagonal is [4, 4, 4, 1.5]. The minimum of the diagonal is 1.5. We can swap row 3 and 4 to get to a new matrix \tilde_A = [4 3 2 1; 1 4 3 2; 2.5 3.5 4.5 1.5; 2 1 4 3]. The new diagonal is [4, 4, 4.5, 3] with a new minimum 3. And in theory, this is the best result I can obtain because there seems no better option: 3 seems to be the max min{d_i}.

In my problem, n is much larger like 1000. I know there are n! row permutations so I cannot go through each permutation in theory. I know greedy algorithm will help--we start from the first row. If a_11 is not the smallest in the first column, we swap a_11 with the largest element in the first column by row permutation. Then we look at the second row by comparing a_22 with all remaining elements in the second column(except a_12). Swap a_22 if it is not the smallest. ... ... etc. We keep doing this till the last row.

Is there any better algorithm to do it?

This is similar to Minimum Euclidean Matching but they are not the same.

Answer 1

Suppose you wanted to know whether there was a better solution to your problem than 3.

Change your matrix to have a 1 for every element that is strictly greater than 3:

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

Your problem can be interpreted as trying to find a perfect matching in the bipartite graph which has this binary matrix as its biadjacency graph.

In this case, it is easy to see that there is no way of improving your result because there is no way of reordering rows to make the diagonal entry in the last column greater than 3.

For a larger matrix, there are efficient algorithms to determine maximal matchings in bipartite graphs.

This suggests an algorithm:

1. Use bisection to find the largest value for which the generated graph has a perfect matching
2. The assignment corresponding to the perfect matching with the largest value will be equal to the best permutation of rows

EDIT

This Python code illustrates how to use the networkx library to determine whether the graph has a perfect matching for a particular cutoff value.

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'

For a random matrix of size 1000*1000 it takes about 1 second on my computer.

Answer 2

Let $x_{ij}$ be 1 if row i is moved to row j and zero otherwise.

You're interested in the following integer program:

max 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

Then plug this into GLPK, Gurobi, or CPLEX. Alternatively, solve the IP using your own branch and bound solve.