0
$\begingroup$

We are given two sets of nodes $A$ and $B$ forming a graph where each element $x \in A$ can be connected with an element $y \in B$ with different possible weights. The graph can be explained in two ways.

  1. There are multiple edges possible between elements of $X$ and $Y$ having different weights.

  2. Elements of $A$ can be matched with repeated nodes of elements of $B$ with different edge weights.

Let $E(x)$ be the set of edges involving element x. Then the maximum weight matching problem can be formulated as follows:

Let $x_{ij}$ takes value 1, if edge $(i, j) \in E$ is selected and $w_{ij}$ be weight of edge $(i, j) \in E$.

$$\text{minimize} \sum_{(i, j) \in E} x_{ij}w_{ij}$$ $$\sum_{j \in E(i)}x_{ij} \le 1 \forall i \in A$$ $$\sum_{i \in E(j)}x_{ij} \le 1 \forall j \in B$$ $$x_{ij} = \{0, 1\} \quad \forall (i, j) \in E$$

My question is whether this problem satisfy the total unimodularity condition. If it does, how can we prove it? I know proof for the standard problem where you consider submatrices and find the determinant.

Can we still use network flow algorithms to solve this problem?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.