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

CC BY-SA 3.0
2015-07-15T19:38:25.230Z
2015-07-15T20:00:38.497Z
2015-07-15T20:00:38.497Z
David Eppstein
<p>Based on the textbook <a href="https://mitpress.mit.edu/books/introduction-algorithms">Introduction to Algorithms</a>, the correctness of a greedy algorithm requires a problem to have two properties:</p>

<ol>
<li>greedy choice property</li>
<li>optimal substructure</li>
</ol>

<p>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?</p>

CC BY-SA 4.0
2024-03-06T18:19:41.977Z
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.
Neal Young
<greedy-algorithms>
What greedy algorithm satisfies greedy choice property but does not have optimal substructure?
Yuan Li
# What greedy algorithm satisfies greedy choice property but does not have optimal substructure?

(Asked by: username_0 on 2015-07-15)

Based on the textbook [Introduction to Algorithms](https://mitpress.mit.edu/books/introduction-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?

**Tags:** greedy-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2015-07-15. Score: 14 | Accepted answer

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


---

