Bipartite graphs with min weights

Question

I have a full bipartite graph with node sets $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. Each node has a weight, $v_i$ for $a_i$ and $w_i$ for $b_i$. Each node $a_i$ is connected to exactly one node of $B$, say $b_j$, via an edge $e_i$, whose weight is $\min(v_i,w_j)$. Now I want to find a one-to-one mapping from $A$ to $B$, whose sum of edge weights is as small as possible.

My idea is to sort $v_i$s increasingly and $w_i$s decreasingly and then find the sum of all $\min(v_i,w_i)$ after sorting. Is it correct? Can you give a proof/disproof?

I have run computer simulations for $n=5,6,\ldots,10$ with random vertex weights and found no counterexample.

Answer 1

It is nice that you have checked your idea on some random samples.

---

To see why your idea work, let us find the simplest but non-trivial case and then take a look at it. For simplicity and WLOG, the weight of a node will be used to denote that node. For example, if $A$ contains a node with weight $42$, that node will be referred to as node 42.

The case of $n=1$ is trivial.

Let $n=2$. If we happens to look at to $A=\{1, 2\}$ and $B=\{3,4\}$, then however we choose the mapping, the sum will be $1+2=3$. This sample is apparently not enlightening.

How about $A=\{1, 3\}$ and $B=\{2,4\}$?

• If we connect 1 with 2 and 3 with 4, the sum is $\min(1,2) + \min(3,4)=1+3=4$.
• If we connect 1 with 4 and 3 with 2, the sum is $\min(1,4) + \min(3,2)=1+2=3$.

So this is a non-trivial example. Now we should ask the basic question, why does the second choice produce a smaller sum?

To answer the question, we should observe how those two sums come up. Note that 1 appears in both sums. Is that coincidence? Think for a moment and you will know it is not. 1 is the minimum number of all numbers. So whatever it is connected to, it will be selected as the weight of the connection.

That means, whatever number 1 is connected to, which is 3 in this case, that number will be missing from later computations, i.e., it will be "wasted". The bigger the "waste" is, the less the remaining numbers will be and hence the less weight the remaining connection will produce, since function $\min(\cdot, \cdot)$ is decreasing with respect to both variables. So 1 should be connected to a number as big as possible. That is why 1 is connected to 4 instead of 3 so as to produce the minimum total sum.

In the case of $n=2$, there are only two choices of the mapping. Either the smaller number in $A$ is mapped to the smaller number in $B$, dubbed "forward mapping", or to the bigger number in $B$, dubbed "reverse mapping". To make the mapping produce smaller total weight, we should always choose the "reverse mapping", so that a large number will be wasted (or, what is the same, a smaller number will be kept to be used.)

---

To prove your idea is correct, we first show that for any mapping from $A$ to $B$, there is a mapping that maps $\min(A)$ to $\max(B)$ with no greater total weight. Suppose map $f$ maps $\min(A)$ to some $b_j$ and some number $a_i$ to $\max(B)$. Then we can make another map $f'$, which is the same as $f$ except for these 4 number, $f'$ maps $\min(A)$ to $\max(B)$ and $a_i$ to $b_j$. Since, as we have shown above, for four numbers $\min(A), a_i$ and $b_j$, $\max(B)$, we have $$ \min(\min(A), \max(B)) + \min(a_i, b_j)\le \min(\min(A), b_j) + \min(a_i, \max(B)),$$ the total weight of $f'$ is not greater than that of $f$.

So we know,

• the minimum total weight comes from a mappings that maps $\min(A)$ to $\max(B)$.
• For all mappings that map $\min(A)$ to $\max(B)$, the minimum total weight comes from, by the same argument, a mapping that maps the minimum of the remaining numbers in $A$ (i.e. the second minimum number in $A$) to the maximum of the remaining numbers in $B$ (i.e., the second minimum number in $B$).
• For all mappings that map $\min(A)$ to $\max(B)$ and the second minimum number in $A$ to the second maximum number in $B$, the minimum total weight comes from a mapping that maps the third minimum number in $A$ to the third maximum number in $B$.
• And so on, until the last minimum number in $A$ is mapped to the last maximum number in $B$, i.e., the maximum number in $A$ is mapped to the minimum number in $B$. $\checkmark$

An even more formal proof could be given. However, the above reasoning might be easier to understand. It should, I believe, convince an ordinary human.

---

Here is another straightforward way to prove your idea.

First assume all numbers are distinct. Let us prove by reductio ad absurdum. Suppose the minimum total weight can be reached by a mapping $g$ other than the mapping described in your idea. Then $g$ must contain a sub-mapping that is a "forward mapping", i.e., there must be two numbers $\alpha_1\lt \alpha_2$ in $A$ and two numbers $\beta_1\lt \beta_2$ in $B$ such that $g(\alpha_1)=\beta_1$ and $g(\alpha_2)=\beta_2$.

Now we can make another mapping $g'$ which is the same as $g$ everywhere else except that the sub-mapping of $g'$ on $\alpha_1$ and $\alpha_2$ is a "reverse mapping", i.e., $g'(\alpha_1)=\beta_2$ and $g'(\alpha_2)=\beta_1$. Now we can, as before, verify that the total weight of $g'$ is smaller than that of $g$, which contradicts our assumption.

If all numbers are not distinct, we will use the technique of approaching by limit. Perturb all numbers slightly so that they become distinct. Now all weights will be slightly off their original weights. That means the total weight obtained from your idea should not be far from the optimal solution. Let the perturbation go to zero, we see that it is, in fact, the optimal solution.

---

You might be interested in a similar problem, how to prove the greedy algorithm that minimize the maximum sum of a pairing.

Answer 2

I think the best solution in here is using the min-cost max-flow algorithm on this graph. If you don't know about it, go and read about it. This algorithm is the most classic solution for this sort of problem.