1
$\begingroup$

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 .

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 29 '18 at 12:54
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Jakube Jul 30 '18 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.