# When does greediness guarantee optimality?

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.

• Check out the notion of a matroid. – Moritz May 25 '17 at 21:14
• If the order of the choices is irrelevant, then greedy algorithms find the optimal solution (e.g. given a set of numbers, find the three element subset with the largest sum). If, at a given state, every option results in the same next state, a greedy algorithm will find an optimal solution. – AlgorithmsX May 25 '17 at 21:25
• @AlgorithmsX, could you elaborate? I didn't quite understand your example. – Xuezhou Zhang May 25 '17 at 21:51
• Did you want a condition to guarantee that you find a minimum, or also that you find the shortest path to the minimum? A sufficient condition for the former: If every local optimum is a global optimum, then the greedy method will find the minimum for you (though not necessarily the shortest path to the minimum). – D.W. May 28 '17 at 3:26
• @D.W., Of course, I want the shortest path as well. – Xuezhou Zhang May 29 '17 at 21:40