0
$\begingroup$

Consider the following optimization problem:

We have n skiers with increasing heights $p_1,...,p_n$ and n skis with increasing heights $s_1,...,s_n$.
We want to minimize the average difference between the height of a skier and his assigned ski.
That is, if skier $p_i$ is assigned $s_{a(i)}$ we want to minimize:
$$\frac1n \sum_{i=1}^n(|\,p_i-s_{a(i)}\,|)$$

(a) Consider the following greedy algorithm. Find the skier and ski whose height di fference is minimized. Assign this skier this ski. Repeat the process until every skier has a ski. Prove of disprove that this algorithm is correct.

(b) Consider the following greedy algorithm. Give the shortest skier the shortest ski, give the second shortest skier the second shortest ski, give the third shortest skier the third shortest ski, etc. Prove of disprove that this algorithm is correct. HINT: One of the above greedy algorithms is correct and one is incorrect for the other. The proof of correctness must be done using an exchange argument.

I had thought that a greedy algorithm was supposed to pick the optimal choice at each step. So, (a) would clearly be a greedy algorithm (even though it is not optimal).

However, I don't understand why (b) is a greedy algorithm. It is optimal, but it does not make the optimal choice at each step. Could someone clarify?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ I'm not sure that "greedy algorithm" is that rigorously defined. We might define it, loosely, as assembling a global solution by incrementally adding components that are locally extremal in some sense. ¶ So, for instance, we might characterize (b) as follows: $1$. Select the shortest skier. $2$. Pair with this skier the skies whose length minus the skier's height is the smallest value (signed, not absolute). $3$. Cross the skier and the skis off their respective lists; if there are skiers and skis remaining, return to step $1$. $\endgroup$ – Brian Tung Jan 19 '16 at 20:46
  • $\begingroup$ @BrianTung Thanks. It does appear that there is no "universal" definition, although it does seem strange to use the term "Greedy" when you are not picking the locally optimum or "best" choice at each step $\endgroup$ – user137481 Jan 21 '16 at 20:12
1
$\begingroup$

As Brian Tung writes in a comment, "greedy algorithm" is not really a crisp technical term, but more of a fuzzy concept that can be helpful for remembering and categorizing algorithms in your mind, and for getting ideas for how to possibly approach a new problem. There are essentially no cases where it makes any technical difference whether you call this-or-that algorithm greedy or not.

That being said, I wouldn't call algorithm (b) a "greedy algorithm" myself, but it's not completely crazy to do so either.

In general, if I were to describe what a greedy algorithm means, my first attempt would be something on the lines of

An algorithm that constructs a solution in little steps, where each step is chosen among the possible step at each time, based on a simple rule to identify which possibility makes the most immediate progress towards the eventual goal.

That certainly describes algorithm (a) -- the rule is simple and selects the way to increase the number-of-skis delivered that leads to the smallest value so far for the sum we want to minimize. That's a reasonable way to measure immediate progress.

On the other hand, if I want to shoehorn (b) into the "greedy paradigm" I would need to weaken my description into

An algorithm that constructs a solution in little steps, where each step is chosen among the possible step at each time, based on a simple rule.

The rule in algorithm (b) is surely simple enough, but it's hard to justify the rule as a short-sighted way to find the most immediate progress -- unless we cheat and already know that the rule happens to construct an optimal solution anyway.

On the other hand, algorithms that match the weakened desciption still have some relevant features in common with actual greedy algorithms -- among which is that the tactics that are useful for proving greedy strategies optimal (when they are indeed optimal), such as exchange arguments, can also be useful to reason about the wider group of algorithms.

So in this sense it is "not completely crazy" to describe (b) as a greedy algorithm, because it can still point towards useful ways to think and reason about the algorithm.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Most textbooks, I've seen used the first definition. However, I also seen other authors state that there is no universal definition. Your second definition, at least for me, would be more of a Heuristic algorithm rather than Greedy, but then I've also seen that definition used by other authors. However, thanks for the answer. $\endgroup$ – user137481 Jan 21 '16 at 19:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.