3
$\begingroup$

The problem has $n$ spears and $n$ soldiers. Spears and soldiers have heights. We want to assign spears to soldiers such that the total height difference of spears and their assigned soldiers is minimum. More precisely, we want to minimize $\sum_{1 \leq i \leq n} |a_{i} - b_{i}|$ where spear $b_{i}$ is assigned to soldier $a_{i}$. A friend of mine proposed the following greedy lemma:

Lemma: There exists an optimal solution where a spear with a minimal height $b_{i} = \min_{1 \leq j \leq n}{ \{ b_{j} \}}$ is assigned to a soldier with a minimal height $a_{j} = \min_{1 \leq j \leq n}\{ a_{j}\}$.

It seems to be the case that for many examples of this problem this lemma holds. However, my friend and I could not prove why. My current knowledge is as follows.

We have the property $\forall_{1 \leq i \leq n}[a_{i} \leq a_{i-1} \land b_{i} \leq b_{i-1}]$ holding in an optimal solution, because the lemma idea is to basically sort the set of spears and soldiers and assign them in parallel in increasing order (i.e. $b_{1}$ to $a_{1}$, $b_{2}$ to $a_{2}$, etc.).

My proof idea is to assume that a solution for this problem does not match spears to soldiers as the lemma describes, but in another way. Then, in such a solution, spear $b_{1}$ would be assigned to soldier $a_{j}: j > 1$ and some other spear $b_{j}$ would be assigned to soldier $a_{1}$. Then, to prove the lemma, I need to prove that $|b_{1} - a_{1}| + |b_{j} - a_{j}| \geq |b_{1} - a_{j}| + |b_{j} - a_{1}|$ holds, i.e., the new sum is at most the old sum. However I am not sure if this inequality can be proven. I think it sometimes does not hold.

$\endgroup$
1
  • $\begingroup$ This is in fact an assignment problem, see en.wikipedia.org/wiki/Assignment_problem, with some additional structure. I'd figure the conjecture is false. To test this, I'd generate lots of soldier-spear problems, rephrase them as assignment problems, solve the assignment problem with say, the Hungarian method, and check if the optimal solution satisfies your lemma. If not, manually assign shortest spear to shortest soldier, resolve the problem and see if the objective value worsens. $\endgroup$
    – Matteo
    Jan 23 at 14:42

1 Answer 1

2
$\begingroup$

Your friend is right, and your idea how to prove it is on the right track. There are two problems with your inequality, though: It’s the wrong way around (the left-hand side is the new sum, and it’s supposed to be at most, i.e. less than or equal to, the old sum, which is the right-hand side), and you can’t assume that $a_j$ and $b_j$ have the same index (at least if what you mean by that is what you wrote in the preceding paragraph, that they have the same rank in order of increasing height), but that doesn’t matter; I’ll just denote them by $a$ and $b$ to simplify the notation. So what we want to prove is

$$ |b_1-a_1|+|b-a|\le|b_1-a|+|b-a_1|\;. $$

Without loss of generality, assume $a_1\le b_1$. Then there are only three possible orders: $a_1ab_1b$, $a_1b_1ab$ and $a_1b_1ba$, and they respectively lead to the following satisfied inequalities:

\begin{eqnarray*} b_1-a_1+b-a\le b_1-a+b-a_1\;,\\ b_1-a_1+b-a\le a-b_1+b-a_1\;,\\ b_1-a_1+a-b\le a-b_1+b-a_1\;. \end{eqnarray*}

$\endgroup$
1
  • 1
    $\begingroup$ Yes you are correct, my bad. I got the inequality in the wrong way. We assume a solution that does not adhere to the lemma, then, make it adhere to the lemma, and argue that the new solution is at least as optimal as the old solution. $\endgroup$ Jan 24 at 9:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .