6
$\begingroup$

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.

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

0

Reset to default

Your Answer

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