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.

  • 10
    $\begingroup$ Check out the notion of a matroid. $\endgroup$
    – Moritz
    Commented May 25, 2017 at 21:14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 25, 2017 at 21:25
  • $\begingroup$ @AlgorithmsX, could you elaborate? I didn't quite understand your example. $\endgroup$
    – Xuezhou Zhang
    Commented May 25, 2017 at 21:51
  • 4
    $\begingroup$ 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). $\endgroup$
    – D.W.
    Commented May 28, 2017 at 3:26
  • 1
    $\begingroup$ @D.W., Of course, I want the shortest path as well. $\endgroup$
    – ChubbyRuby
    Commented May 29, 2017 at 21:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.