3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So you want to order the rows and columns so that $\alpha$ times the minimal diagonal element is at least the maximal off-diagonal element. Stated differently, you want $\alpha x \geq y$ for every diagonal element $x$ and off-diagonal element $y$. $\endgroup$ – Yuval Filmus Mar 21 '16 at 18:53
  • $\begingroup$ Yes. That is what I would like to have. $\endgroup$ – Ribz Mar 21 '16 at 18:55
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.