0
$\begingroup$

There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:

There are n tasks, each task t_i has a weight w_i and a length l_i. Find an order of tasks t_1, ... t_j, ..., t_n that minimizes the total cost of completion, where the cost of completion of each task is c_j * w_j, where c_j is the time it has passed since you started working on the first task until you finished the jth task.

If we analyze the problem a bit, we can see that the task that we choose to complete first will impact the cost of all the remaining tasks. For example, say you only have 2 tasks:

task_1 with w_1 = 1 and l_1 = 5 and

task_2 with w_2 = 4 and l_2 = 2

If we started first task_1, its cost would be 5 * 1 = 5 while if we started first task_2, its cost would be 2 * 4 = 8. But, the cost of completing task_2 after task_1 is (5+2) * 4 = 28. This shows clearly that the order of completion of one task affects the cost of completion of all the remaining tasks.

Considering how each task we decide to complete next impacts the cost of all the remaining tasks, it startles me that the best order is simply the order we get by sorting the tasks by their ratio w_i/l_i.

Which part of the problem hints that the solution doesn't require to check all the possible orders?

The problem is taken from Algorithms Illuminated 3 by Tim Roughgarden.

$\endgroup$
4
  • $\begingroup$ It's not really clear what you're asking. Why can this problem be solved using a greedy algorithm? because we can prove that the solution yielded this way works. How did we get the intuition that this should work? Possibly by looking at many instances, possibly by luck, but most likely, by an educated guess: this seems like a plausible solution, so we try to prove it's correct, and if we manage to prove that (which we do), then we're done. $\endgroup$
    – Shaull
    Sep 29 '20 at 17:57
  • $\begingroup$ Could you say then which part of the problem informs your educated guess over applying a greedy algorithm? Finding a greedy solution is not a hint, but the solution itself. Before trying to apply the greedy technique, there should be some hints that support the idea. Which are those hints? $\endgroup$ Sep 29 '20 at 18:00
  • 1
    $\begingroup$ Sure - the ratio $w_i/l_i$ is the "weight per time unit" of each task, it makes sense to order the tasks by this, and to see what happens... $\endgroup$
    – Shaull
    Sep 29 '20 at 18:02
  • $\begingroup$ That’s the same reasoning presented on the book. I have the feeling that we could derive the solution more systematically. I’ll keep looking... $\endgroup$ Sep 29 '20 at 18:15
4
$\begingroup$

In this case: It is obvious that you start with some task immediately, start a second task as soon as the first task is finished, then start a third task immediately after this etc.

It is obviously that you can swap the order of two consecutive tasks without affecting any other task. In an optimal solution, swapping the order of two consecutive tasks cannot improve the solution.

Now you look for a criterion when swapping two tasks would improve the solution. For an optimal solution, that criterion must fail for any two consecutive tasks. And lucky enough there is a simple criterion.

So any problem where tasks must be performed consecutively, and where swapping two tasks doesn't affect all the other tasks, you can solve if you can determine which order of the two tasks is better.

This doesn't work for the travelling salesman problem for example, because swapping two cities affects other cities as well.

$\endgroup$
2
  • $\begingroup$ Allow me to try to prove your argument: Say you have n tasks in some random order O_1, then you could try to improve this order by swapping if necessary the last two tasks and obtain a new order O_2. Then, you could try to improve order O_2 by swapping if necessary the third last and the second last tasks; you can do this without looking at the last task because the swapping of two tasks doesn’t impact the cost of the later tasks. Continue until you try to swap the first two tasks, and start over again and again until there are no more swaps that improve the order. $\endgroup$ Sep 29 '20 at 23:24
  • $\begingroup$ The reason why this process terminates, and therefore works, is that after you try to swap the first two tasks, the task that results in first place will remain there (because the ordering is transitive) and therefore you are left with only n-1 tasks to reorder. But, then, wouldn’t it need to be also the case that the ordering is transitive for this to work? $\endgroup$ Sep 29 '20 at 23:29
1
$\begingroup$

Generally speaking, we have a few standard paradigms for designing algorithms: divide-and-conquer, dynamic programming, greedy algorithms, and reduction to an existing known problem. When you have no idea how to solve a problem, one useful strategy is to try each of those paradigms in turn for a little while: spend a little time looking for a divide-and-conquer algorithm, spend a little time looking for a dynamic programming time algorithm, spend a little time looking for a greedy algorithm, and so on. With practice, you may be able to develop a feeling for which paradigms are most likely to be suitable for any particular problem and let you direct your energy, but as a starting point (or if you have no particular hunch), then you can try each one of them.

Now when you spend time looking for a greedy algorithm, usually if a greedy algorithm exists, it will be very simple. Most problems can't be solved with greedy algorithms, but the ones that can, usually have a very simple algorithm. There's a basic approach to finding greedy algorithms: you brainstorm a few plausible candidates (usually there are a few natural ones), then check each one to see if it is correct. See How to prove greedy algorithm is correct for methods to check whether a candidate greedy algorithm is correct. Usually, you can quickly eliminate most candidates that aren't correct (e.g., because they don't pass random testing). So, if you get lucky and one of your candidates is actually a correct algorithm, usually you'll be able to quickly get some confirmation that it looks very promising.

With all of that background, I can answer your question. How would you find this algorithm? You'd find it by spending a little time on each major algorithm design paradigm, including greedy algorithms; and you'd have a good chance of finding the particular order if you brainstorm for candidates, and likely you'll come up with this as one of the candidates. How would you avoid looking for complicated solutions first? There's no silver bullet, but it's often helpful to spend a little time on each paradigm before spending too long on any one paradigm. Also, as you get more practice, you may find that you develop an intuition or sense for which paradigms are most worth trying, for any particular problem, which might guide you in this particular case to make sure to try a few greedy algorithms. In this case, it's pretty easy to see how I might make a "greedy" choice at each step, without regard to its future consequences, so it's natural to try a greedy algorithm whenever you have a sequence of choices to make.

$\endgroup$

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.