Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?

Question

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.

Answer 1

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.

Answer 2

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.