Following what is stated in the question Why is greedy algorithm not finding maximum independent set of a graph?, I have the following question:
Even enumerating and testing all possible choices of the greedy algorithm (namely, when there are two possible choices, test both) and verifying which returns the highest value, can it return an approximate result? (ignoring the computational cost)