One rigorous idea which is similar to your question is to look for the largest "transversal" of the matrix. A transversal is a collection of entries of the matrix with one entry from each row and column. The terms in the determinant of the matrix are multiplicative transversals, but for this question, you would be interested in the maximum additive transversal. There are polynomial time algorithms to find the largest transversal. You can view it as the optimum marriage problem, or as a min-cut, max-flow problem, but it ultimately comes from the fact that you are maximizing a linear functional (the value of the transversal) on the Birkhoff polytope, which is the convex hull of the permutation matrices. As such, it is a linear programming problem. The remaining question is how best to speed it up further, using the fact that it is a special case rather than general linear programming. There is a noted paper on this subject, On Algorithms for Obtaining a Maximum Transversal, by Duff.
Note that the question isn't an either-or between the diagonal and the anti-diagonal. There are many things that a transversal can do other than be close to the diagonal or anti-diagonal. Even so, you can look at how close the transversal is to one or the other extreme. For instance, you can look at its inversion number. The diagonal has the smallest inversion number, 0, while the antidiagonal has the unique largest inversion number, $n(n-1)/2$.
A slightly different idea is to look at correlations between the inversion number and the value of the transversal. I think some types of correlation can also be computed in polynomial time.
No comments:
Post a Comment