A group of n guests shows up to a house for a party, but some pairs of guests are enemies. There are two rooms in the house, and the host wants to distribute guests among the rooms, breaking up as many pairs of enemies as possible. The guests are all waiting outside the house and are impatient to get in, so the host needs to assign them to the two rooms quickly, even if this means that it's not the best possible solution.
(a)We constructed a greedy 1/2-approximation algorithm for this problem that runs in time O(V +E) prior. Now give a randomized algorithm that achieves (in expectation) the same approximation guarantee in time O(V ).
(b) Your solution in part (a) probably had to flip O(V ) random coins, but coins are expensive, use hashing to give an algorithm that only flips O(logV) random coins.