I was wondering if there is any theoretical results characterizing under what condition does greedy algorithm actually finds the optimal solution.Here is a motivating example. Suppose you are trying to find$$\min_{x \in \mathbb{Z}^2} f(x)$$where $f$ is convex, and the minimizer happens to be on an integer point $(a,b)$. You start from $(0,0)$ and at each iteration you are allowed to walk to one of the 4 integer points next to you.The greedy algorithm is that, at each iteration $t$, you check the 4 points and walk to the one with the lowest objective value.Now, here is a condition under which greedy method actually gives you the shortest path to find the minimum:For any $x_1$, $x_2$, such that $f(x_1)\leq f(x_2)$, we have $min_{x \mbox{ next to } x_1} f(x)\leq min_{x \mbox{ next to } x_2} f(x)$.So can the above condition be generalized to other settings? Or are there any general conditions that characterize such optimality? Quick google search didn't give me anything useful.
When does greediness guarantee optimality?
algorithms;optimization;greedy algorithms;searching;matroids