# what is the significance of the word “Sub-problems” in Greedy Method?

With respect to Dynamic Programming we make a statement that :

Greedy algorithm have a local choice of the sub-problems whereas Dynamic programming would solve the all sub-problems and then select one that would lead to an optimal solution.

Now in Dynamic Programming we have some problem with recursive nature which we solve by solving the sub-problems and then obtain the global optimum but in case of Greedy approach we do not solve the problem in any recursive nature rather we find a feasible solution at every stage with the hope of finding optimal solution.

So I am unable to get the notion of sub-problems in case of Greedy Approach .

• It's best to look at some examples. The text is supposed to help you, so if it doesn't, you can just ignore it. – Yuval Filmus Jul 29 '18 at 12:54

Here is a concrete example, the problem of Set Cover:

Set Cover

Input: Sets $S_1,\ldots,S_m$ whose union is $U$

Output: Minimal-size subset of $\{S_1,\ldots,S_m\}$ whose union is $U$

The well-known greedy algorithm for this problem (which gives a $\ln n$ approximation) proceeds as follows:

• While $U \neq \emptyset$:
1. Add to the solution the largest set $S_i$.
2. Remove all elements of $S_i$ from all sets and from $U$.

Having chosen a set $S_i$, we are effectively moving to another Set Cover instance, in which the sets are $T_j := S_j \setminus S_i$, and the universe is $V := U \setminus S_i$.

This new instance is the sub-problem mentioned in your statement. The greedy choice — largest set — is the local choice mentioned in your statement.

To check your understanding, show that this view is appropriate for other well-known greedy algorithms such as Huffman encoding and the greedy algorithm for interval scheduling.

• For completeness: this greedy algorithm doesn't actually compute the optimal set subset, only an approximation. The set cover problem is in fact NP-hard. – Jakube Jul 30 '18 at 13:28