We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size.
For example if the following matrix is given:
1000 0010
1101 0111
1101 0111
1101 0111
We should output 9 because the biggest rectangle we can get is with size 9. We are allowed to swap any columns infinite number of times and we are only requested to find the maximum size of the subrectangle.
Can we solve this problem faster that trying all possible permutations?
-
$\begingroup$ What's the best algorithm you have been able to find so far? What approaches have you tried? What's the context where you encountered this problem? Please credit the source of this problem in the question. $\endgroup$D.W.– D.W. ♦2018年04月17日 22:30:57 +00:00Commented Apr 17, 2018 at 22:30
-
$\begingroup$ The problem is not given on english, also I still haven't found working algorithm rather than not proven greedys $\endgroup$someone12321– someone123212018年04月18日 07:30:43 +00:00Commented Apr 18, 2018 at 7:30
1 Answer 1
Yes, you can solve it faster than trying all possible permutations.
The biggest such rectangle must span consecutive rows. So, for all $i,j$ with $i \le j,ドル check what is the biggest rectangle you can make that spans rows $i..j$. You can do this check in $O(mn)$ time, by checking which columns have a 1 in all of those rows. There are only $O(m^2)$ possible values of $i,j$.
So, the running time of this simple method is $O(m^3 n),ドル which is faster than trying all permutations. (Trying all permutations would take $\Omega(m \cdot n!)$ time, which is far slower -- it is exponential time, rather than polynomial time.) I make no claim that this simple method is optimal -- rather, I merely claim that the answer to your question is "yes".
-
$\begingroup$ Can we speed up this method $\endgroup$someone12321– someone123212018年04月19日 07:25:03 +00:00Commented Apr 19, 2018 at 7:25