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.


migrated from math.stackexchange.com May 27 '17 at 12:33

This question came from our site for people studying math at any level and professionals in related fields.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.