# Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?

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?

• May 18, 2011 at 4:49

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. 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” (SIAM J. Discrete Math. 6, pp. 274-283), Helman, Moret and Shapiro gave a formal description of just this (called a 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 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.

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

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 ivotron: if you didn't mean my first interpretation I will delete this answer.

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

• Greedoids (like matroids) are simply a special case of matroid embeddings. May 19, 2011 at 10:38