suppose we have a weighted grid graph and our problem is to find maximum independent set. There is a greedy algorithm that each time choose the heaviest node and remove it and its neighbors until all nodes of G have been chosen or removed. we want to prove that W(s) >= 1/4 W(T) where S is our greedy result and T is the OPT solution.
let S be the result of our greedy algorithm and T be an arbitrary independent set which can be the OPT. We know that for any T for any node v which belongs to T-S there exist a node v' in S which is neighbor of v and w(v) <= w(v').
Is there any idea to how prove that?
The desired result can be obtained with the following proof.
Let S be the set generated by the greedy algorithm, let T be an independent set of maximal weight. We will stepwise transform T into S and bound the loss for each transformation step.
Choose v in T\S with maximal weight. By the statement included in the question above, there exists v' in S such that w(v') >= w(v); choose such a v'. Let N be the neighbourhood of v' in T; N contains v and at most 4 vertices (as we have a grid graph). As v was chosen with maximal weight and w(v')>=w(v), we obtain w(v')>=w(N)/4. We set T':=(T\N) and add v' to it. By construction, T' remains an independent set and we have w(T') >= w(T) - (3/4)w(N).
In total, for each exchange step, vertices from T\S get eliminated, but a node from S is added such that the added total weight is at least one quarter of the lost total weight.
Furthermore, the constructed sets N in each step are disjoint, which means that in each step, at least one quarter of w(N) is preserved. In total, as we have constructed S, andS has weight at least (1/4)w(T).
Note that the input graph is not required to be a grid graph but maximum degree 4 is sufficient; furthermore, the proof can be generalized by permitting an abitrary graph, replacing 4 by the maximum degree Δ yielding an approximation ratio of 1/Δ.