Finding the densest n * n submatrix in a sparse matrix

I have a sparse square matrix with a side of 2 * n.

eg.

1,0,0,1,0,1
0,1,1,1,0,1
1,0,0,0,1,1
0,0,1,1,0,0
1,1,1,0,0,0
0,0,0,1,1,0

      

And I need an efficient way to find the n * n submatrix with the largest number of 1s.

I found several ways to do this, but not faster than O (n ^ 4). I also found faster ways without requiring the submatrix to be n * n.

EDIT: The submatrix must be contiguous,

+3


source to share


1 answer


Based on your application for an O (n ^ 4) -time algorithm, my guess is that the submatrix must be contiguous, since otherwise the problem is NP-hard (it's harder than biclik detection). For the O (n ^ 2) -time algorithm, it suffices to perform O (n ^ 2) preprocessing, which allows O (1) -time queries of the form "given a, b, c, d

, compute sum_{i=a}^b sum_{j=c}^d X[i,j]

".

Given an array X[1..m,1..n]

, compute the array Y[0..m,0..n]

as follows.



initialize Y to the zero array
for i from 1 to m
    for j from 1 to n
       Y[i,j] = Y[i-1,j] + X[i,j]
    end
end
for i from 1 to m
    for j from 1 to n
       Y[i,j] = Y[i,j-1] + Y[i,j]
    end
end

      

Now Y[c,d] = sum_{i=1}^c sum_{j=1}^d X[i,j]

. To calculate sum_{i=a}^b sum_{j=c}^d X[i,j]

, use the inclusion of exception Y[c,d] - Y[a-1,d] - Y[c,b-1] + Y[a-1,b-1]

.

+3


source







All Articles