Why is a greedy approach correct for solving problem ANCOIMP in June challenge '15 ?

general
, , ,
1

I solved the problem by first checking for a bipartite graph using the input matrix and if the graph was bipartite, I went on to find a way to color it so that the product of the number of vertices in both colors is maximized.
For the latter problem we have pairs (a,b) for each connected component of the bipartite graph representing the number of vertices which should go into each color/side.Now,the problem was to find a division such that the number of vertices are as even as possible.

To solve this first sort on the basis of number of vertices in each component in descending order, and then start filling up the sets such that the greater of a or b always goes into the set which has less vertices.

For eg.

Let the pairs be : (5,1),(3,1),(2,1) (sorted)

Initially the sets are (0,0).

After adding (5,1) -> (5,1)

After adding (3,1) -> (6,4)

After adding (2,1) -> (7,6)

Surprisingly, this solution got accepted but, I could never prove the correctness of this algorithm.

So my question is whether this approach is indeed correct or was the test data for the problem weak ?

Here’s a link to my solution link

EDIT : So it is established that the greedy approach is wrong and that the test data was weak. We’ve also got plenty of counter examples and a dynamic programming algorithm in the answers. Thank you @lebron @Amlesh and @thezodiac1994.
Now some one please close the question as I don’t have enough karma to do it :stuck_out_tongue:

2 Likes
2

Your second part can’t be correct - this task is at least as hard as 0-1 knapsack problem, which is NP-complete. So you can’t solve it in a greedy way :slight_smile:

Here is an example for you: (9,1),(7,1),(6,1),(6,1),(5,1).

Correct partition is (9,1),(7,1),(1,6),(1,6),(1,5), which gives you 19 vertices on both sides.

However, your solution will do:

  • (0,0)+(9,1)=(9,1)
  • +(1,7)=(10,8)
  • +(1,6)=(11,14)
  • +(6,1)=(17,15)
  • +(1,5)=(18,20).

So it is all about test data being weak.

4 Likes
3

This is essentially a knapsack problem, where you’re given pairs of numbers instead, and you want one of the partitions to be as close as possible to half the number of total vertices. Consider the following case:

Initial pair: (0, 0),
Input Pairs: (6, 1), (5, 6), (4, 10)

Your greedy algorithm would add them as follows: (6, 1) + (5, 6) + (4, 10) = (15, 17)

Whereas the optimal solution is: (6, 1) + (6, 5) + (4, 10) = (16, 16).

One can solve this with a knapsack DP algorithm. Let poss[i, j] represent whether it is possible for the left partition to have exactly i vertices after using the first j pairs. Then:

 pos[i, j] = pos[i, j-1] (If you can achieve i vertices without using the jth pair) OR
             pos[i - pair[j].first, j-1] (if the left value in the jth pair goes into the left partition) OR
             pos[i - pair[j].second, j-1] (if the right value of the jth pair goes in to the left partition)

Now since you want to maximize the product of the vertices in the final partitions, you achieve the value that’s as close as possible to half the total number of vertices (i.e. If N is the number of pairs, find v where poss[v, N] = true and v is as close to hals the total number of vertices).

3 Likes
4

What I can make out is you tried to solve the partition problem greedily. This should fail on certain test cases so we can assume the test data is weak.

Read on the greedy soln. It says the greedy soln gives a 7/6 approximation.

Here is a failing test case for your approach -

Sorted Set = { (9,1) , (8,1) , (7,1) , (6,1) , (5,1) }

Greedy way
(9,1) + (1,8) = (10,9)
(10,9) + (1,7) = (11,16)
(11,16) + (6,1)= (17,17)
(17,17) + (5,1)= (22,18)

Correct soln is
(9,1) + (8,1) = (17,2)
(17,2) + (1,7) = (18,9)
(18,9) + (1,6) = (19,15)
(19,15) + (1,5) = (20,20)

You can use dynamic programming to achieve this.

1 Like