Let f : 2E R be a normalized submodular function. We associate a weight wi 0 with each i E. Consider the following linear program:

maximize wixi iE

subject to xi f(A), A E iA

Show that this problem can be solved by the following greedy algorithm: (1) Sort elements of E and rename them so that wi w2 wn. (2)A0 ;fork1tondoAk {1,2,...,k}. (3)Fork1tondoxi f(Ai)f(Ai1).

I need a detailed answerthanks