1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You mean makespan, i.e., the instant the machine that ends latest finishes, by "cost", don't you? What is the $s_j$ speed? For an unlimited supply of machines, the way out is perhaps just to run each job on a machine, and shuffle long jobs to fast machines. $\endgroup$ – vonbrand Mar 8 at 19:27
  • $\begingroup$ @vonbrand Maybe that is the usual interpretation, but I'm just thinking of it as each machine has a constant associated with it, $p_i$. A small $p_i$ means jobs that run on that machine have lower cost since for a given job with constant $s_j$, we have that $s_j \cdot p_i$ will be small. And then each job has a constant associated with it, $s_j$. A small $s_j$ will result in a smaller cost $s_j \cdot p_i$ for a given machine $p_i$. The reason the greedy algorithm makes since intuitively is we want to pair large $p_i$ with small $s_j$, and vice versa to minimize the sum of the $s_j \cdot p_i$. $\endgroup$ – kanso37 Mar 9 at 3:00
  • $\begingroup$ you will have to clarify a lot here. $\endgroup$ – vonbrand Mar 9 at 15:38
  • $\begingroup$ @vonbrand Not sure what I need to clarify. You have a clearly defined objective function which you want to minimize. (If the objective function was the confusing part I just updated the post.) $\endgroup$ – kanso37 Mar 9 at 17:14
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Realized later that this exchange argument isn't as uncommon as I thought! Just never had seen it before in the context of greedy algorithms :P $\endgroup$ – kanso37 Mar 11 at 1:41

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.