5
$\begingroup$

In all the exampls of the greedy algorithms I've seen so far, such as activity selection problem and unit-sized set coverage problem, the algorithm is usually very simple and intuitive and returns the first set that satisfies the constrain under greedy strategy.

For example, in the activity selection problem, all we need to do is to go down the list and keep finding solution of the type $d_i$ > $f_j$, and the first list that returns (even if it is near empty) is considered the greedy solution.

My question is that this strategy doesn't even take into consideration of any other case which may be better, is this the signature of greedy algorithm?

Thanks

Improve this question
$\endgroup$
1
  • $\begingroup$ In principle, picking the second should well be possible. $\endgroup$
    – Raphael
    Commented Dec 18, 2014 at 9:34

2 Answers 2

Reset to default
6
$\begingroup$

Yes, this is the idea of greedy algorithms, also known as myopic algorithms. There is still a lot of freedom in deciding what the myopic choice is based on. Allan Borodin has developed a theory of priority algorithms formalizing the notion of greedy algorithm. Such a theory can be used to analyze what greedy algorithms cannot do.

Sometimes greedy algorithms give good results, sometimes they don't. When they do, the corresponding algorithm is very simple and fast. When they don't, we have to use more complicated algorithms. Here good results doesn't necessarily mean optimal results. The greedy algorithm for maximum coverage doesn't produce optimal results, only a $1-1/e$ approxmation – but this is also the best one can do in polynomial time (in the worst case), so the greedy algorithm is optimal with respect to the worst case approximation ratio.

Improve this answer
$\endgroup$
0
2
$\begingroup$

interestingly there are two simple greedy algorithms that produce optimal solutions, and others exist. they produce the 1st solution which is also optimal. one way to understand this is to think about global vs local optima. if there is only one global optima, it is also a local optima, and a greedy algorithm can find it.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Local optima are more relevant for local search. $\endgroup$
    – Yuval Filmus
    Commented Dec 18, 2014 at 2:19
  • $\begingroup$ right. greedy algorithms are basically quite analogous to local search. $\endgroup$
    – vzn
    Commented Dec 18, 2014 at 2:23
  • $\begingroup$ That's an interesting point of view. Local search algorithms could take many iterations to converge, and always move from solution to solution. A good example is the simplex algorithm. Greedy algorithms, on the other hand, involve partial solutions, and converge very quickly. $\endgroup$
    – Yuval Filmus
    Commented Dec 18, 2014 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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