<p>Yes, there is such work. Allan Borodin with coauthors developed a theory where they formalize the notion of greediness and obtain results which approximation ratios can be reached with them. They introduce a class of priority algorithms, which generalizes greedy algorithms. Their first work on this topic is 
the paper "<a href="http://scholar.google.com/scholar?q=%22%28Incremental%29%20Priority%20Algorithms%22&amp;hl=en&amp;btnG=Search&amp;as_sdt=1,5">(Incremental) Priority Algorithms</a>".</p>

<p>P.S. The previous paragraph answers on a different question: Is it possible to prove that, for a given problem, no greedy algorithms exist with approximation ratio less than some $1+\epsilon$? What concerns the question I suppose it is assumed there that optimal means exact so the question relates to problems in P (I assume greedy algorithms have polynomial complexity though I guess this is not necessary) which are known to have solution by other methods than greedy ones. And I don't know the answer on this question.</p>

<p>To ivotron: if you didn't mean my first interpretation I will delete this answer.</p>

CC BY-SA 3.0
2011-05-18T08:46:46.543Z
2011-05-18T11:54:38.847Z
2011-05-18T11:54:38.847Z
Oleksandr Bondarenko
<p>See this also:
<a href="http://en.wikipedia.org/wiki/Greedoid" rel="nofollow">http://en.wikipedia.org/wiki/Greedoid</a></p>

CC BY-SA 3.0
2011-05-19T10:38:54.413Z
Greedoids (like matroids) are simply a special case of matroid embeddings.
Magnus Lie Hetland
CC BY-SA 3.0
2011-05-18T09:00:22.320Z
2011-05-18T09:00:22.320Z
László Kozma
<p>The simplest thing to do would be to set up the greedy algorithm for the problem, and then look for a counter-example. If you find one, you've got your answer. Otherwise there are <a href="http://www.idi.ntnu.no/~mlh/algkon/greedy.pdf" rel="nofollow noreferrer" title="Proof methods and greedy algorithms">many ways of proving that greed works</a>. There are some issues with this, of course (such as how specifically to formulate the greedy algorithm). As for characterizing which problems can and which problems can't be solved greedily, there is a general answer to that, too.</p>

<p>In fact, in their paper <a href="http://dx.doi.org/10.1137/0406021" rel="nofollow noreferrer" title="An Exact Characterization of Greedy Structures">“An Exact Characterization of Greedy Structures”</a> (<em>SIAM J. Discrete Math</em>. <strong>6</strong>, pp. 274-283), Helman, Moret and Shapiro gave a formal description of just this (called a <a href="http://en.wikipedia.org/w/index.php?title=Matroid_embedding&amp;oldid=291417382" rel="nofollow noreferrer" title="Matroid Embedding">matroid embedding</a>, which generalizes both matroids and greedoids). From the abstract: “The authors present exact characterizations of structures on which the greedy algorithm produces optimal solutions.”</p>

<p>In general, the greedy algorithm can be formulated in terms of weighted set systems $(E,\mathcal{F},w)$. You have a set $E$ (for example, the edges, in the case of minimum spanning trees), and you have a set $\mathcal{F}\subseteq 2^E$ of subsets of $E$ (think partial spanning forests, for the problem of minimum spanning trees). $\mathcal{F}$ represents the valid partial solutions constructed by combining elements from $E$. There is also the weight function, $w$, which gives you the weight or cost of any element in $\mathcal{F}$. We usually assume this to be linear—i.e., each element in $E$ has a weight, and the weights of the (partial) solutions are just the sum of the element weights. (For example, the weight of a spanning tree is the sum of its edge weights.) In this context, Helman et al. showed that the following are equivalent:</p>

<ol>
<li><p>For every linear objective function, $(E,\mathcal{F})$ has an optimal basis.</p></li>
<li><p>$(E,\mathcal{F})$ is a matroid embedding.</p></li>
<li><p>For every linear objective function, the greedy bases of $(E,\mathcal{F})$ are exactly its optimal bases.</p></li>
</ol>

<p>In other words: For structures such as these (which basically embody the kind of structures usually thought of when working with greed), exactly the set of matroid embeddings can be solved greedily.</p>

<p>The definition of a matroid embedding isn't all that hard, so proving that a given problem is or is not a matroid embedding is certainly feasible. The <a href="http://en.wikipedia.org/w/index.php?title=Matroid_embedding&amp;oldid=291417382" rel="nofollow noreferrer" title="Matroid Embedding">Wikipedia entry</a> gives the definition quite clearly. (Understanding the proof why these are the exact structures solvable by greed—that’s another matter entirely…)</p>

<p>If your problem can be formulated in terms of selection from a weighted set system with a linear objective function, and if you can show that it is <em>not</em> a matroid embedding, then you have showed that it cannot be solved greedily, even if you haven't been able to find a counter-example. (Although I suspect finding a counter-example would be quite a bit easier.)</p>

<p>This approach isn't entirely without problems, I suppose. As you say, the general idea of greed is rather informal, and it might well be possible to tweak it in such a way that the formalism of linearly weighted set systems doesn't apply.</p>

CC BY-SA 3.0
2011-05-19T06:58:51.030Z
2017-07-27T12:28:31.217Z
2017-07-27T12:28:31.217Z
Magnus Lie Hetland
<p><em>Greedy</em> is a non-formal term, but it could be (not sure, that's why I'm asking) that for certain problems, greediness can be mathematically formulated and thus be proven that no optimal greedy algorithm exist. Is this possible?</p>

CC BY-SA 3.0
2011-05-18T04:49:31.957Z
Yes, see: http://en.wikipedia.org/wiki/Greedy_algorithm#Cases_of_failure.
Sadeq Dousti
<ds.algorithms><greedy-algorithms>
Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?
ivotron
# Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?

(Asked by: username_0 on 2011-05-18)

*Greedy* is a non-formal term, but it could be (not sure, that's why I'm asking) that for certain problems, greediness can be mathematically formulated and thus be proven that no optimal greedy algorithm exist. Is this possible?

**Tags:** ds.algorithms, greedy-algorithms

> **Comments:**
> **username_1**: Yes, see: http://en.wikipedia.org/wiki/Greedy_algorithm#Cases_of_failure.  

---

## 3 answers

### Answer by username_4 on 2011-05-19. Score: 9 | Accepted answer

The simplest thing to do would be to set up the greedy algorithm for the problem, and then look for a counter-example. If you find one, you've got your answer. Otherwise there are [many ways of proving that greed works](http://www.idi.ntnu.no/~mlh/algkon/greedy.pdf "Proof methods and greedy algorithms"). There are some issues with this, of course (such as how specifically to formulate the greedy algorithm). As for characterizing which problems can and which problems can't be solved greedily, there is a general answer to that, too.

In fact, in their paper [“An Exact Characterization of Greedy Structures”](http://dx.doi.org/10.1137/0406021 "An Exact Characterization of Greedy Structures") (*SIAM J. Discrete Math*. **6**, pp. 274-283), Helman, Moret and Shapiro gave a formal description of just this (called a [matroid embedding](http://en.wikipedia.org/w/index.php?title=Matroid_embedding&oldid=291417382 "Matroid Embedding"), which generalizes both matroids and greedoids). From the abstract: “The authors present exact characterizations of structures on which the greedy algorithm produces optimal solutions.”

In general, the greedy algorithm can be formulated in terms of weighted set systems $(E,\mathcal{F},w)$. You have a set $E$ (for example, the edges, in the case of minimum spanning trees), and you have a set $\mathcal{F}\subseteq 2^E$ of subsets of $E$ (think partial spanning forests, for the problem of minimum spanning trees). $\mathcal{F}$ represents the valid partial solutions constructed by combining elements from $E$. There is also the weight function, $w$, which gives you the weight or cost of any element in $\mathcal{F}$. We usually assume this to be linear—i.e., each element in $E$ has a weight, and the weights of the (partial) solutions are just the sum of the element weights. (For example, the weight of a spanning tree is the sum of its edge weights.) In this context, Helman et al. showed that the following are equivalent:

1. For every linear objective function, $(E,\mathcal{F})$ has an optimal basis.
2. $(E,\mathcal{F})$ is a matroid embedding.
3. For every linear objective function, the greedy bases of $(E,\mathcal{F})$ are exactly its optimal bases.

In other words: For structures such as these (which basically embody the kind of structures usually thought of when working with greed), exactly the set of matroid embeddings can be solved greedily.

The definition of a matroid embedding isn't all that hard, so proving that a given problem is or is not a matroid embedding is certainly feasible. The [Wikipedia entry](http://en.wikipedia.org/w/index.php?title=Matroid_embedding&oldid=291417382 "Matroid Embedding") gives the definition quite clearly. (Understanding the proof why these are the exact structures solvable by greed—that’s another matter entirely…)

If your problem can be formulated in terms of selection from a weighted set system with a linear objective function, and if you can show that it is *not* a matroid embedding, then you have showed that it cannot be solved greedily, even if you haven't been able to find a counter-example. (Although I suspect finding a counter-example would be quite a bit easier.)

This approach isn't entirely without problems, I suppose. As you say, the general idea of greed is rather informal, and it might well be possible to tweak it in such a way that the formalism of linearly weighted set systems doesn't apply.


---

### Answer by username_2 on 2011-05-18. Score: 10

Yes, there is such work. Allan Borodin with coauthors developed a theory where they formalize the notion of greediness and obtain results which approximation ratios can be reached with them. They introduce a class of priority algorithms, which generalizes greedy algorithms. Their first work on this topic is
the paper "[(Incremental) Priority Algorithms](http://scholar.google.com/scholar?q=%22%28Incremental%29%20Priority%20Algorithms%22&hl=en&btnG=Search&as_sdt=1,5)".

P.S. The previous paragraph answers on a different question: Is it possible to prove that, for a given problem, no greedy algorithms exist with approximation ratio less than some $1+\epsilon$? What concerns the question I suppose it is assumed there that optimal means exact so the question relates to problems in P (I assume greedy algorithms have polynomial complexity though I guess this is not necessary) which are known to have solution by other methods than greedy ones. And I don't know the answer on this question.

To username_0: if you didn't mean my first interpretation I will delete this answer.


---

### Answer by username_3 on 2011-05-18. Score: 1

See this also:
<http://en.wikipedia.org/wiki/Greedoid>

> **Comments:**
> **username_4**: Greedoids (like matroids) are simply a special case of matroid embeddings.  

---

