snippetMinor
How to find a perfect matching with this constraint?
Viewed 0 times
thishowwithperfectconstraintfindmatching
Problem
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.
$$\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.
Solution
We consider three different cases: $\alpha 1$.
Suppose first that $\alpha x_{m+1}$. If $m = n$ then we are back to the previous case. If $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.
Suppose first that $\alpha x_{m+1}$. If $m = n$ then we are back to the previous case. If $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.
Context
StackExchange Computer Science Q#54747, answer score: 3
Revisions (0)
No revisions yet.