15
$\begingroup$

Based on the textbook Introduction to Algorithms, the correctness of a greedy algorithm requires a problem to have two properties:

  1. greedy choice property
  2. optimal substructure

It is easy to come up with counter examples for which a greedy solution fails due to the lack of the greedy choice property, e.g. the 0/1 knapsack problem. But I find the other possibility pretty hard to imagine. Can anybody give me a problem and a corresponding greedy algorithm which satisfies the first property but not the second?

$\endgroup$
1
  • $\begingroup$ Somewhat relatedly, there is a subtlety in the presentation of this material: we often think of "optimal substructure" as meaning that in any optimal solution, the solution to every subproblem is necessarily optimal (consider, e.g. shortest paths). However, for correctness of a greedy algorithm, what one really needs is the converse: with the correct greedy choice, for the solution to be optimal, it suffices for the subproblem solution(s) to be optimal. The same issue arises in dynamic programming. This subtlety is often a source of confusion when teaching these algorithms. $\endgroup$
    – Neal Young
    Commented Mar 6 at 18:19

1 Answer 1

14
$\begingroup$

One of the standard estimators in robust statistics is a type of trimmed mean where you choose a majority subset of a set of input numbers in such a way as to minimize the maximum difference between any two selected numbers, and then take the mean of the selected subset. There's an easy greedy-choice first step: choose the median as part of your subset. But once you've made that choice, the remaining problem is not of the same type (i.e. we don't have optimal substructures), so there's no obvious method of continuing this algorithm greedily. In particular it doesn't work to keep choosing medians of the remaining points. (The repeated greedy median strategy, done with a little care, gives the interquartile mean which is also robust but does not solve the same problem and has a lower breakdown point.)

$\endgroup$

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.