[Solved]: Do all greedy algorithm produce just the first solution, no matter how bad it is?

Problem Detail: 

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

Asked By : John Swoon

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35436

 Ask a Question

 Download Related Notes/Documents