30 Greedy algorithm for Partitioning problem

Problem Definition

• Given $2N$ distinct real numbers $x_1,x_2,\cdots ,x_{2n-1},x_{2n}$
• Want to partition there numbers into $n$ pairs $P_1,P_2,\cdots P_n$ (of two numbers each) which minimises the maximum sum of two numbers in a pair

Greedy Algorithm

• Sort the numbers in increasing order, say $y_1<y_2\cdots y_{2n-1}<y_{2n}$
• Then our desired ordering is one which pairs $y_i$ with $y_{2n+1-i}$ for each $1\le y\le n$

Proof

• We claim that $y_1$ can be paired with $y_{2n}$
• Suppose $y_1$ is paired with $y_i$ and $y_j$ is paired with $y_{2n}$
• Note that $y_1<y_j$ and $y_i<y_{2n}$
• Hence, $y_1+y_i<y_j+y_{2n}$
• Swap $y_1$ and $y_j$: so the pairs are now $\{y_1,y_{2n}\}$ and $\{y_i,y_j\}$
  • $y_1+y_{2n}<y_j+y_{2n}$ because $y_1<y_j$
  • $y_i+y_j<y_j+y_{2n}$ because $y_i<y_{2n}$