Hi this comes from Algorithg Design by Jon Kleinberg and Éva Tardos chapter 11 q

Question

Hi this comes from Algorithg Design by Jon Kleinberg and Éva Tardos chapter 11 question 10. Help would be appreciated.

Suppose you are given an n x n grid graph G, as in Figure 1 Associated with each node v is a weight w(v), which is a nonnegative integer. You may assume that the weights of all nodes are distinct. Your goal is to choose an independent set S of nodes of the grid, so that the sum of the weights of the nodes in S is as large as possible. (The sum of the weights of the nodes in S will be called its total weight.) Consider the following greedy algorithm for this problem The "heaviest-first" greedy algorithm Start with S equal to the empty set While some node remains in G Pick a node vi of maximum weight Add vi to S Delete vi and its neighbors from G End while Return S (a) Let S be the independent set returned by the "heaviest first greedy algorithm, and let T be any other independent set in G. Show that, for each node v e T either v e S, or there is a node v S so that w(v) s w(v') and (v, v') is an edge of G (b) Show that the "heaviest-first" greedy algorithm returns an independent set of total weight at least1 times the maximum total weight of any independent set in the grid graph G Figure 1. A grid graph.

Explanation / Answer

Algorithm Explanation

How does heaviest - first greedy Algorithm works (Each node (v) has weight w(v) )?

1. Given a Graph G , we have to find an independent set S of G such that sum of weights of All the nodes in G have the maximum weight.
2. Pick a node V of Max weight , Add into our Set (S)
3. Delete all the neighbours of V , repeat until Graph has no nodes

Solution Explanation

A) Given two Sets S and T , S is returned by our Heaviest first Algorithm and T is any independent Set in G
So for each node V belongs to T , either V is present in S or There is another node V' that belongs to S such that
W(V) <= W(V') and there is an Edge between (V,V')

Lets say V does not belong to S and it belongs to T , which means during our algorithm V was Deleted when we had chosen some node (V' ) which would be having more weight than V and must be neighbour of V.
That means W(V) <=W(V')


B) We have to prove That S that is returned by Our algorithm follows 4 * W (Sum of all nodes in S) = W(Sum of all nodes in T)

Lets take an element v that belongs to T, we try to find the similar node v whether it belongs to S or not

1. If v belongs to S then it means v's own weight is counted , If not then By above defintion there must be a node V' that belongs to S and its weight must be greater that equal to weight of v i.e  W(V) <=W(V')

2. Now if v is present in S that means there are other four neighbours (because its a grid , single node has 4 neighour) of weight less that equal to v which means w(sum of all the neighbours of v ) is at most 4*w(v) and they do adds up for total weight of T .

Hence we can say that our algorithm returns an independent set of total weight at least one fourth times the maximum total weight of any independent set T in graph G   

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.