Greedy Algorithm - Exchange Argument
Consider the following problem :
Input: $2n$ positive integers (repetitions allowed) $l_1,l_2, ..., l_{2n}$.
Output: $n$ pairs $(l_{11}, l_{12}), (l_{21}, l_{22}), ..., (l_{n1}, l_{n2})$ such that $\sum_{j=1}^{n} l_{j1}\cdot l_{j2}$ is maximal.
My solution is to pick the 2 largest integers from the input on each greedy iteration, and it will provide the maximal sum ($\sum_{j=1}^{n} l_{j1}\cdot l_{j2}$).
I'm trying to proof the correctness of the algorithm using exchange argument by induction, but I'm not sure how to formally prove that after swapping an element between my solution and the optimal solution, I have a solution which is not worse than before.
I'll appreciate any direction.
Thanks.
$\endgroup$1 Answer
$\begingroup$Here's a way to see that your solution is maximal (though not necessarily maximum, for that see the comments on this answer):
Let $a\geq b\geq c\geq d$.
Then we have that $$(ab+cd)-(ac+bd)=a(b-c)+d(c-b)=(a-d)(b-c)\geq 0$$ with equality iff $b=c$ or $a=d$. However, in either case the "swap" only exchanges equal numbers. Similarly, we have that $$(ab+cd)-(ad+bc)=a(b-d)+c(d-b)=(a-c)(b-d)\geq 0$$ with equality iff $a=c$ or $b=d$. However, in either case the "swap" only exchanges equal numbers.
$\endgroup$ 13
