title: Find the "largest" dense sub matrix in a large sparse matrix
body: <p>Given a large sparse matrix (say 10k+ by 1M+) I need to find a subset, not necessarily continuous, of the rows and columns that form a dense matrix (all non-zero elements). I want this sub matrix to be as large as possible (not the largest sum, but the largest number of elements) within some aspect ratio constraints.</p>
  
  <p><em>Are there any known exact or aproxamate solutions to this problem?</em></p>
  
  <p>A quick scan on Google seems to give a lot of close-but-not-exactly results. <em>What terms should I be looking for?</em></p>
  
  <hr>
  
  <p><em>edit:</em> Just to clarify; the sub matrix <em>need not be continuous</em>. In fact the row and column order is completely arbitrary so adjacency is completely irrelevant.</p>
  
  <hr>
  
  <p>A thought based on Chad Okere's idea</p>
  
  <ol>
  <li>Order the rows from largest count to smallest count (not necessary but might help perf)</li>
  <li>Select two rows that have a "large" overlap</li>
  <li>Add all other rows that won't reduce the overlap</li>
  <li>Record that set</li>
  <li>Add whatever row reduces the overlap by the least</li>
  <li>Repeat at #3 until the result gets to small</li>
  <li>Start over at #2 with a different starting pair</li>
  <li>Continue until you decide the result is good enough</li>
  </ol>