Heuristics for a matrix symmetrization problem

Bora Uçar

Abstract. We consider the following problem: given a square, nonsymmetric, (0,1)-matrix, find a permutation of its columns that yields a zero-free diagonal and maximizes the symmetry. The problem is known to be NP-hard. We propose a fast iterative-improvement based heuristic and evaluate the performance of the heuristic on a large set of matrices.

Key words. unsymmetric sparse matrices, bipartite matching, matrix symmetrization.