Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines

Question

I'm trying to prove a greedy algorithm works for a specific problem:

You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run all the jobs.) Each job $j$ has a size $s_j$. Each machine $i$ has a constant associated with its speed, $p_i$. The cost of running job $j$ on machine $i$ is simply $s_j \cdot p_i$. We can only assign at most $k$ jobs to one machine. How should the jobs be assigned to minimize the sum of the costs on all machines (that have been given jobs)? I.e., minimize $\sum_{i,j} s_j \cdot p_i$ over all assignments of a job $j$ to a machine $i$. (Note that there is no penalty for assigning lots of jobs to a specific machine. We aren't trying to balance out the number of jobs assigned to each machine.)

The simple greedy algorithm is to first sort the jobs from greatest size to least size, and the machines from fastest (least $p_i$ in this case) to slowest, and then assign the $k$ largest jobs to the fastest machine, second $k$ largest jobs to the second fastest machine, etc. (So in other words, pair off large $s_j$ with small $p_i$ and vice versa.)

I'm now trying to prove this algorithm is correct. My first try was to show that the greedy algorithm stays ahead. I reasoned that the optimal algorithm must also use the fastest machines (or else it is trivial to show it isn't actually optimal), and therefore if we look at the machines from fastest to slowest, we can consider the first job for which they differ. But then it isn't necessarily true that the greedy algorithm is doing better at this point as the optimal algorithm could minimize cost for that specific slot by putting in a smaller job (even though it actually hurts it later).

I also tried doing an overall induction on the number of jobs. Say we show it it optimal for $n$ jobs. Can we show it is optimal for $n+1$ jobs given the same options for machines? Again, it isn't clear how to make this argument since we can't just slide in job $n+1$; maybe the optimal assignment suddenly follows a wildly different pattern.

Thanks for the help!

Answer 1

It is easy to see the fastest $m=\lceil n/k\rceil$ machines are used. Suppose the speeds of these machines are $p_1\le p_2\le\cdots \le p_m$, then we want to minimize $$p_1s_{\sigma(1)}+\cdots+p_1s_{\sigma(k)}+p_2s_{\sigma(k+1)}+\cdots+p_2s_{\sigma(2k)}+\cdots+p_ms_{\sigma(n)}$$ over all permutations $\sigma$.

By the rearrangement inequality, the sum above is minimized when $s_{\sigma(1)}\ge s_{\sigma(2)}\ge\cdots\ge s_{\sigma(n)}$, so your greedy algorithm is indeed correct.

Answer 2

I figured it out. Turns out the solution is deceptively simple, but in the details it is somewhat different than proofs I have seen for other greedy algorithms. We basically show that any output besides the one the greedy algorithm returns can be improved further.

To do this, consider two jobs with sizes $s_j$ and $s_i$ such that $s_j > s_i$. Furthermore, consider two machines with constants $p_l, p_k$ such that $p_l > p_k$. We show that the best way of assigning $s_j, s_i$ to $p_l, p_k$ is to assign $s_j$ (the larger job) to $p_k$ (the faster machine) and $s_i$ (the smaller job) to $p_l$ (the slower machine). Since there are only two possible assignments, in other words we want to show $$s_j \cdot p_k + s_i \cdot p_l \le s_j \cdot p_l + s_i \cdot p_k$$

To do so we set $s_i = x, s_j = x+a, p_k = y, p_l = y + b$ for some $x,y,a,b \ge 0$. So equivalently we want to show $$(x+a)\cdot y + x \cdot (y + b) \le (x + a)(y + b) + xy$$

This can be seen simply by simplifying. Thus we have shown that for two jobs and two machines, cost is minimized by assigning the larger job to the faster machine and the smaller job to the slower machine.

It quickly follows that the greedy algorithm is optimal because for any other output, there will be a pair of assignments that don't satisfy the "larger job to faster machine, smaller job to slower machine" rule. And thus by switching the assignments of this pair, we lower the total cost.