[Math] Greedy Strategy for assigning skis to skiers

algorithms

We have n skiers with increasing heights $p_1,…,p_n$ and n skis with increasing heights $s_1,…,s_n$.
We want to minimize the average difference between the height of a skier and his assigned ski.
That is, if skier $p_i$ is assigned $s_{a(i)}$ we want to minimize:
$$\frac1n \sum_{i=1}^n(|\,p_i-s_{a(i)}\,|)$$

Consider the following Greedy Strategy:

$\qquad$Give the shortest skier the shortest ski, give the second
shortest skier the second shortest ski,
$\qquad$give the third shortest skier the third shortest ski, etc.

The following is a proof by contradiction that the strategy is optimal:

If the greedy algorithm is not optimal, then there is some input $p_1,…,p_n, s_1,…,s_n$ for which it does not produce an optimal solution.

Let the optimal solution be $T = \{ (p_1, s_{j(1)}),…,(p_n, s_{j(n)}) \}$
Let the output of the Greedy algorithm be $G = \{ (p_1, s_1),…,(p_n, s_n) \}$

1) Beginning with $p_1$, compare $T$ and $G$.
2) Let $p_i$ be the first person who is assigned different skis in $G$ than in $T$.
3) Let $s_j$ be the pair of skis assigned to $p_i$ in $T$.
4) Create solution $T'$ by switching the ski assignments of $p_i$ and $p_j$.

By definition of the Greedy Algorithm, $s_i \le s_j$.
The total cost of $T'$ is given by:

$Cost(T')=Cost(T)-\frac1n (|p_i-s_j|+|p_j-s_i|-|p_i-s_i|-|p_j-s_j|)$

Since $p_i \le p_j$ and $s_i \le s_j$ there are 6 possible cases to consider:

Case 1: $p_i \le p_j \le s_i \le s_j$
Case 2: $p_i \le s_i \le p_j \le s_j$
Case 3: $p_i \le s_i \le s_j \le p_j$
Case 4: $s_i \le s_j \le p_i \le p_j$
Case 5: $s_i \le p_i \le s_j \le p_j$
Case 6: $s_i \le p_i \le p_j \le s_j$

In all cases, we can show that:

$(|p_i-s_j|+|p_j-s_i|-|p_i-s_i|-|p_j-s_j|) \ge 0$

which would be a contradiction that $T$ is optimal.

I don't understand step 4 of the proof where it says:
$\qquad$Create solution $T'$ by switching the ski assignments of $p_i$ and $p_j$.

In $T$,$\,$$p_j$ is assigned $s_{j(j)}$.
The proof appears to be assuming that $s_{j(j)}=s_i$.
Shouldn't we be saying switch the assignments in $T$ of $p_i$ and whatever $p_k$ is assigned $s_i$?

Could someone clarify? Thanks!

Best Answer

Related Solutions

[Math] Greedy Algorithm Proof

We have a set of jobs $J_i = (a_i, b_i)$ where all the $a_i,b_i \ge 0$. We want to find the permutation $\pi$ which minimises $$\max_j \left\{ b_{\pi(j)} + \sum_{k \le j}a_{\pi(k)} \right\}$$

Suppose we have proven that for all job sets $X$ of size no greater than $n$ the permutation which sorts the jobs by descending $b_i$ breaking ties by descending $a_i$ is an optimal solution (bearing in mind that there may be more than one optimal solution). (Call this ordering doubly-reverse-lexicographical because it sorts in descending order starting from the right).

Consider a job set $Y$ of size $n+1$ whose "worst" job is $J_{n+1}$, and suppose that there is no optimal solution in which this job comes first. Of the optimal solutions select one which puts $J_{n+1}$ as early as possible, in position $j^* = \pi^{-1}(n+1) > 0$. Now, which $j$ maximises the expression above (i.e. which job finishes last)?

Given that $b_{\pi(j^*)}$ is maximal by construction and the sum is non-decreasing the maximising $j$ must be $\ge j^*$. Also, if the maximising $j > j^*$ we can move $J_{n+1}$ to the start without affecting the optimality, so by contradiction that's impossible. We're forced to conclude that $J_{n+1}$ is the job which finishes last.

Now consider what happens if we swap it with the job before it. Call that job $J_p$ for previous. $J_p$'s finishing time increases from $b_p + \sum_{k < j^*}a_{\pi(k)}$ to $b_p + \sum_{k \le j^*}a_{\pi(k)} \le b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ and $J_{n+1}$'s finishing time decreases from $b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ to $b_{n+1} + \sum_{k \le j^* \wedge k \ne j^*-1}a_{\pi(k)}$ so we have a contradiction with this being an optimal solution which puts $J_{n+1}$ as early as possible.

We've now proven that there is an optimal solution for $Y$ in which $J_{n+1}$ comes first. Either some of these optimal solutions allow for the rest of the jobs to be ordered non-optimally because the worst job is so bad that it doesn't matter – in which case putting them in an optimal ordering will give an optimal ordering – or the rest of the jobs must be optimally ordered to get an optimal ordering. In either case we can apply our strong inductive presupposition to say that there is an optimal ordering which is doubly-reverse-lexicographical.

The base case of only one job is trivial.

[Math] Using induction to show a greedy algorithm always makes the optimal task selection

Well, I don't want to be picky, I'll just assume that the tasks given are sorted with regard to their ending times, i.e. $f_i \leq f_{i+1}$ (or you could just sort the input).

The first thing you would like to do is to decide why you can use induction. Does the problem contains similar, but smaller subproblems? In our case it does, but it is not clear from the code you have given, i.e. you would need to argue why running last $n-1$ runs of the loop is similar to runing them all (this is kind of trivial, but tedious if it were to be done formally).

To make it easier, consider the following rewrite:

procedure selection($s_i, s_{i+1}, ...,s_n$, $f_i,f_{i+1},...,f_n$)
if n < i
  return (empty set)
else
  j = i+1
  while task j is incompatible with S and j <= n
      j = j + 1
  return {i} U selection($s_j, s_{j+1}, ..., s_n$, $f_j, ..., f_n$)

This recursive version gives a clear indication where the subproblem structure is, and it is much easier to work with. For example you can read-off the base case: it is for an empty input (the first if-clause). You can also guess what your assumption should be: selection works for all $|S| \leq n-j+1$, but you don't know $j$, so it has to work for all $|S| \leq n-1$. All that is left, is to observe that $f_i$ has to be smaller or equal of the finish time of the corresponding task in the optimal solution. From there follows that the remaining set $s_j, \ldots, s_n$ is the largest possible worth considering, and the rest is implied by the step's assumption.

In my timezone it is getting late, so please consider this a huge hint, try to work out the rest on your own and leave a comment whether you succeeded; if not, I shall complete this answer tomorrow.

Best Answer

Related Solutions

[Math] Greedy Algorithm Proof

[Math] Using induction to show a greedy algorithm always makes the optimal task selection

Related Question