What greedy algorithm satisfies greedy choice property but does not have optimal substructure?

Question

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?

Answer 1

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.)