Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
  1. I was wondering what kinds of optimization problems can be solved by greedy algorithms accurately?
  2. I don't understand the following quote from Wikipedia:

    Greedy algorithms can be characterized as being 'short sighted', and as 'non-recoverable'. They are ideal only for problems which have 'optimal substructure'.

    If I am correct, an optimization problem with 'optimal substructure' can accurately be solved by dynamic programming method, not always by greedy algorithms. So what does "greedy algorithms are ideal only for problems which have 'optimal substructure'" mean?

Thanks and regards!

share|cite|improve this question
Have you seen this before? – Srivatsan Sep 6 '11 at 4:56

Optimal substructure means that optimising every part of the structure will give an optimal solution for the whole structure.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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