what is the significance of the word "Sub-problems" in Greedy Method?
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$:


Add to the solution the largest set $S_i$.
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 &mdash; largest set &mdash; 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.