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!