World's most popular travel blog for travel bloggers.

Min-max the component-wise sum of two sets

, , No Comments
Problem Detail: 

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?

Asked By : hengxin

Answered By : Yuval Filmus

Let $f$ be an optimal solution in which $f(a_1) < f(a_2)$ for some $a_1 < 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) & a = a_1, \\ f(a_1) & a = a_2, \\ f(a) & \text{otherwise}. \end{cases} $$ Then $$ \begin{align*} a_1 + g(a_1) &= a_1 + f(a_2) < a_2 + f(a_2), \\ a_2 + g(a_2) &= a_2 + f(a_1) < a_2 + f(a_2), \\ a + g(a) &= a + f(a) & \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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback