Search code examples
greedyproof

How to prove that Greedy approaches will not work


For any given problem where greedy approaches will not give optimal value, we can find a counter example to disprove that approach.

However, is it possible to prove that for a given problem, any greedy approach in general will not work.


Solution

  • The most general answer I can come up with is that any greedy algorithm will find local optima. If a problem has several local optima where only one of them represent the global optimum, then any greedy algorithm might get stuck at one of the local optima.

    To find a counter example all you have to do is figure out an instance of the problem that has such local optimum, and construct it so that you "trick" the algorithm into that local optimum.

    I don't think there's a general way of showing that a greedy approach will not work. The best way to refute an algorithm is probably to find a counter example where it doesn't produce the correct result.