wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Minimum lines to cover
        
(Message started by: bazinga on Oct 15^th, 2012, 10:06pm)

Title: Minimum lines to cover
Post by bazinga on Oct 15^th, 2012, 10:06pm

Given a 2-d array of 1' and 0's , give an algorithm to find minimum number of horizontal/vertical lines to cover all the zeros.

[hideb]
For each position of zero check whether the number of 0's are greater in row or col. If row has more 0's draw one horizontal line otherwise if col has more 0's draw a vertical line. If 0's are equal in all rows and columns then arbitrarily break the tie.
Is this correct?
[/hideb]

Title: Re: Minimum lines to cover
Post by towr on Oct 16^th, 2012, 10:28am

It doesn't give the optimal solution for
0 0 0
1 1 0
1 0 1
0 1 1
Three vertical lines will cover all zeroes, but if you start with a horizontal line (covering the greatest numbers of zeroes to start with), you still need three additional lines.

To start with, I'd look at each row/column that has only one 0, and then draw a line perpendicular through it. Because you need a line through that 0 anyway, and you may cross off extra ones this way. So it's a no-lose step. That doesn't provide a complete solution though.
Perhaps it'd work if, when you get stuck, you make a greedy choice (a line through most uncovered zeroes).

Title: Re: Minimum lines to cover
Post by Aryabhatta on Oct 17^th, 2012, 9:26am

This is the minimum vertex cover problem for bi-partite graphs and has known fast solutions.

See this lecture: http://lucatrevisan.wordpress.com/2011/02/23/cs261-lecture14-algorithms-in-bipartite-graphs/