World's most popular travel blog for travel bloggers.

How to find a perfect matching with this constraint?

, , No Comments
Problem Detail: 

I have a positive integer $n$ and two disjoint sets of nodes $V=\{v_1,\ldots,v_n\}$ and $W=\{w_1,\ldots,w_n\}$. I also have a weight function $f:V\times W\to\mathbb{R}_{>0}$ and a positive number $\alpha$. The function $f$ is represented by the matrix $\mathbf{F}=\left[f_{vw}\right]$ as:

$$\mathbf{F}=\begin{bmatrix} f_{11} & \cdots & f_{1n} \\ \vdots & \ddots & \vdots \\ f_{n1} & \cdots & f_{nn} \\ \end{bmatrix}.$$

I would like to create a perfect matching between $V$ and $W$ (that is associate one node from $V$ to exactly one node from $W$) such that some constraint is satisfied (it is given explicitly next). Or, I am looking for a function $a:V\to W$ that is bijective between $V$ and $W$.

The constraint is specified by a matrix $\mathbf{G}=\left[g_{vw}\right]$ defined by: $g_{vw}=f_{va(v)},\forall v,w$. For example, if I have $n=3$, $v=\{1,2,3\}$ and $W=\{1,2,3\}$ and $\mathbf{F}$ is given by: $$\mathbf{F}=\begin{bmatrix} 1 & 3 & 2 \\ 4 & 7 & 1 \\ 7 & 9 & 5 \\ \end{bmatrix},$$ and the bijection is $a(1)=2,a(2)=3,a(3)=1$. The matrix $\mathbf{G}$ will be: $$\mathbf{G}=\begin{bmatrix} 3 & 2 & 1 \\ 7 & 1 & 4 \\ 9 & 5 & 7 \\ \end{bmatrix}.$$

Now, the constraint says that $\alpha\min\limits_{v}g_{vv}\geqslant\max\limits_{v\neq w}g_{vw}$. With the same example, if $\alpha=1$, the bijection $a$ does not satisfy the constraint since $\alpha\min\limits_{v}g_{vv}=1$ and there exists some $w\neq v$ such that $g_{vw}>1$.

In summary, I would like to find a bijection between $V$ and $W$, $a:V\to W$, such that $$\alpha\min\limits_{v}g_{vv}\geqslant\max\limits_{v\neq w}g_{vw},$$ where $g_{vw}$ is defined previously.

Asked By : Riebuoz
Answered By : Yuval Filmus

We consider three different cases: $\alpha < 1$, $\alpha = 1$, and $\alpha > 1$.

Suppose first that $\alpha < 1$. Arrange the $n^2$ elements in the matrix in non-increasing order: $x_1,x_2,\ldots$. Note that $x_1,\ldots,x_n$ must belong to the diagonal, and moreover $\alpha x_n \geq x_{n+1}$. Hence the instance is solvable iff $\alpha x_n \geq x_{n+1}$ and $x_1,\ldots,x_n$ belong to different rows and columns.

The case $\alpha = 1$ is very similar. Let $x_1 = x_2 = \cdots = x_m > x_{m+1}$. If $m = n$ then we are back to the previous case. If $m < n$, then $x_1,\ldots,x_m$ must belong to the diagonal. We find out whether it is possible, fix this part of the permutation, and iterate (details left to you). The most interesting case is when $m > n$. In that case, we use a bipartite perfect matching algorithm to find out whether $n$ of these $m$ elements can be put on the diagonal.

The case $\alpha > 1$ is slightly more complicated. Let $A$ be the list of elements larger than $\alpha x_n$. All of these elements (if any) must belong to the diagonal in any solution, since the diagonal always contains an element at least as small as $x_n$. If $A \neq \emptyset$, we first check that they can be put in the diagonal, fix this part of the permutation, and iterate. If $A = \emptyset$, then we check whether the first $n$ elements can be put on the diagonal. If so, we have found a solution. Otherwise, we know that the solution must contain an element at least as small as $x_{n+1}$ on the diagonal, and we let $A$ be the list of these elements. If $A \neq \emptyset$, we do what we did before. Otherwise, we use a bipartite perfect matching algorithm to try and fit $x_1,\ldots,x_{n+1}$ on the diagonal (deleting first elements conflicting with the current partial permutation). If so, we have found a solution. Otherwise, we continue with $x_{n+2}$. Eventually we will have made a conclusion, since when reaching $x_{n^2}$ the answer is positive.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54747

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback