A way to prove that there is no greedy algorithm that gets the optimal solution?
The question is pretty simple. I need to prove that there is no greedy algorithm that can get the optimal solution for a given problem.
It is not clear to me if there is any condition that the problem must match in order for a certain greedy algorithm to exist to obtain an optimal solution. Or, if there is a sufficient condition that the problem is not solvable by a greedy algorithm.
I'm definitely talking about greedy coloring:
source to share
I need to prove that there is no greedy algorithm that can get the optimal solution for a given problem.
Well it depends on the definition of the property you selected.
Look, for example, at a graph coloring problem and suppose you have an oracle M
that gives a partially colored graph, returns true if and only if there is a graph coloring for it.
Now using this oracle, the greedy algorithm could be as follows:
for each vertex v:
for each color c:
temporarly color v with c
run M on partially colored graph
if M yields true, make c constant to v, and abort the inner loop
The above algorithm colors the graph in a greedy way while using one vertex at a time according to the oracle's answer M
. (Choosing the best answer M
and assigning it to each vertex and color where many answers are false or true)
Do I feel this cheating? Probably because there isn't one M
that runs in polynomial time, but if you run the exponential algorithm that creates M
, there is definitely a greedy algorithm for it.
However, you can prove that there is no KNOWN algorithm that eagerly chooses in polynomial time (or any other polynomial algorithm for that matter) that gives the optimal answer for coloring the graph, since the coloring of the graph is NP-Complete, t knows any algorithm , which effectively solves the problems of NPCs (and most believe that this does not exist).
However, if at some point we prove P = NP, we can compute efficiently M
and we get an efficient greedy algorithm that will resolve the coloring of the graph.
source to share
Greed, on a philosophical level, is a phenomenon where the owner of an attribute thinks in the short term and ignores long term returns. As we can see, this is not a clear concept. How is the algorithm greedy? If we do not know the essence of his greed, then we have no means to prove that it does not receive an optimal solution. Moreover, the concept of obtaining an optimal solution is ambiguous. This may mean that he will never get an optimal solution, or it may mean that there is at least a case where he cannot get an optimal solution. I suggest you document the problem, understand the problem, and then start thinking about how to prove it again.
source to share