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

  • In principle, picking the second should well be possible. – Raphael Dec 18 '14 at 9:34
up vote 6 down vote accepted

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.

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.

  • 1
    Local optima are more relevant for local search. – Yuval Filmus Dec 18 '14 at 2:19
  • right. greedy algorithms are basically quite analogous to local search. – vzn Dec 18 '14 at 2:23
  • 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. – Yuval Filmus Dec 18 '14 at 2:51

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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