2
$\begingroup$

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 1

Reset to default
1
$\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
  • $\begingroup$ Doesn't this only take care of pairings that have a "Hamming distance" of $2$? In other words, suppose the greedy algorithm has thus far paired $a$ and $b$, and $c$ and $d$. Now we see integers $e$ and $f$. What if the optimal pairing was $a$ and $f$, $b$ and $c$, and $d$ and $e$? $\endgroup$ Commented Apr 4, 2017 at 20:41
  • $\begingroup$ @BrianTung Yes it does, but that's how I understand "maximal" in this context. I'm not claiming (and the OP isn't asking) that this is the maximum. But it is maximal. $\endgroup$ Commented Apr 4, 2017 at 20:43
  • $\begingroup$ It comes from the "rearangment inequality" (don't know if you say it like this in english) : if $x_1,\dots,x_n$ and $y_1,\dots,y_n$ are two strictly positive sequences, then $$\sum x_iy_i \le \sum x_{\sigma(i)}y_{\psi(i)}$$, where $(x_{\sigma(i)})_i$ and $(y_{\sigma(i)})_i$ are the ordered sequences extracted from $(x_i)$ and $(y_i)$. It can be proved by induction. $\endgroup$ Commented Apr 4, 2017 at 21:08
  • $\begingroup$ @NicolasFRANCOIS I think your inequality is the wrong way around. $\endgroup$ Commented Apr 4, 2017 at 21:14
  • $\begingroup$ @adfriedman : are you sure ? $2\times 3+5\times 1=11<17=1\times 2+3\times 5$, so to maximize the sum of products, you have to put the two sequences in the same order... $\endgroup$ Commented Apr 4, 2017 at 21:19

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.