How to find a perfect matching with this constraint? 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}_{&gt;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} &amp; \cdots &amp; f_{1n} \\
\vdots &amp; \ddots &amp; \vdots \\
f_{n1} &amp; \cdots &amp; 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 &amp; 3 &amp; 2 \\
4 &amp; 7 &amp; 1 \\
7 &amp; 9 &amp; 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 &amp; 2 &amp; 1 \\
7 &amp; 1 &amp; 4 \\
9 &amp; 5 &amp; 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}&gt;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.
We consider three different cases: $\alpha &lt; 1$, $\alpha = 1$, and $\alpha &gt; 1$. 

Suppose first that $\alpha &lt; 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 &gt; x_{m+1}$. If $m = n$ then we are back to the previous case. If $m &lt; 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 &gt; 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 &gt; 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.