Min-max the component-wise sum of two sets When I was trying to prove a problem at hand to be NP-complete, I coined the following problem:


  Given two integer sets $A = \{ a_1, \cdots, a_n \}$ and $B = \{ b_1, \cdots, b_n \}$.
  We know that there are $n!$ bijections between $A$ and $B$. 
  For a bijection $f\colon A \to B$, define 
  $$\max f = \max_{a \in A} \{ a + f(a) \}.$$
  This problem is to find a bijection which minimizes $\max f$.


I think it is polynomial solvable (which is thus of no use in reduction).
The algorithm is simple: Sort $A$ non-decreasingly and $B$ non-increasingly and map $A$ to $B$ component-wisely.

However, I could not find a proof.

Problem: How to prove (or disprove) this algorithm?
Let $f$ be an optimal solution in which $f(a_1) &lt; f(a_2)$ for some $a_1 &lt; a_2$. Let $g$ be obtained from $f$ by switching the values at $a_1$ and $a_2$:
$$
g(a) = \begin{cases} f(a_2) &amp; a = a_1, \\ f(a_1) &amp; a = a_2, \\ f(a) &amp; \text{otherwise}. \end{cases}
$$
Then
$$
\begin{align*}
a_1 + g(a_1) &amp;= a_1 + f(a_2) &lt; a_2 + f(a_2), \\
a_2 + g(a_2) &amp;= a_2 + f(a_1) &lt; a_2 + f(a_2), \\
a + g(a) &amp;= a + f(a) &amp; \text{otherwise}.
\end{align*}
$$
It follows that $\max g \leq \max f$.

Consider now $f$ as a permutation on $\{1,\ldots,n\}$: the first element is the index of $f(a_n)$, the second element is the index of $f(a_{n-1})$, and so on. It is a classical result that $f$ can be sorted by transposing pairs of numbers in the wrong order, an operation which corresponds to the transformation above (one way is to put $n,n-1,\ldots,2$ in their right place, if needed, in this order). The correctness of your algorithm immediately follows.

Comment: This sort of analysis is very reminiscent of the analysis of greedy algorithms.