  In this paper, we introduce the Maximum Matrix Contraction problem, where we
aim to contract as much as possible a binary matrix in order to maximize its
density. We study the complexity and the polynomial approximability of the
problem. Especially, we prove this problem to be NP-Complete and that every
algorithm solving this problem is at most a $2\sqrt{n}$-approximation algorithm
where n is the number of ones in the matrix. We then focus on efficient
algorithms to solve the problem: an integer linear program and three
heuristics.
