Hi there,

I've spent some time on this exercise and can't seem to solve it concisely - I'd appreciate your help!

Suppose you are given a graph G where every node is adjacent to at most k other nodes. Associated with each node v is an integer weight w(v) 2 0. You may assume that all the weights are distinct. Your goal is to choose an independent set S of nodes, 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 Start with S-0. While some node remains in G: - Pick a node v of maximum weight. -Add v to S - Delete v and its neighbors from G Endwhile. Show that this algorithm returns an independent set of total weight at least total weight of any independent set in the graph G. times the maximum