2
$\begingroup$

Consider having two sets $L$ (left) and $R$ (right). $R$ nodes have a capacity limit. Each edge $e$ has a cost $w(e)$.

I want to map each of the $L$ vertices to one node from $R$ (one-to-many matching), with minimum total edge-costs.

Each vertex in $L$ must be mapped to one vertex in $R$ (but each node in $R$ can be assigned to multiple $L$-nodes).

Examples: Consider the capacity of $R$ nodes is $2$.

1) This is NOT correct, since one node from $L$ has not assigned to a node in $R$.

enter image description here

2) This is NOT correct, since the capacity of a node in $R$ is violated.

enter image description here

3) This IS correct. All $L$ nodes are assigned to a node in $R$, and the capacity of $R$ nodes is not violated.

enter image description here

Any idea how can I solve this?

$\endgroup$
4
$\begingroup$

This problem is called the B-matching problem. Where you are given a function $b:V \rightarrow \mathbb{N}$ that assign a capacity to each vertex and a function $u:E \mapsto \mathbb{N}$ that assigns a weight to each edge.

The problem is solvable in polynomial time. An easy solution is to reduce the problem to minimum weight maximum matching. Create $b(v)$ copies of each vertex $v$ and connect each of them to all neighbors of the original vertex v. We get a polynomial time reduction, since for $b(v) \geq \mathrm{deg}(v)$ we can set $b(v) := \mathrm{deg}(v)$ since we can not match $v$ with more vertices than its neighborhood anyway and that each of its neighbors is matched with at most one vertex in your special case.

$\endgroup$
  • 1
    $\begingroup$ First, I would like to have different $b$ per vertex. Second, consider this example: if $b(v)=5$, I can match $(i,v)=2, (j,v)=3$. I can also match $(p,v)=2, (q,v)=2, (r,v)=1$. What happens in this case? I also have a condition that all the $L$ nodes must be matched with something. How it can be handled in $b$-matching? $\endgroup$ – mcqueenvh Dec 16 '19 at 12:51
  • 1
    $\begingroup$ I mean $v \in L, \forall v$ must be matched and maximum with one node from $R$. $\endgroup$ – mcqueenvh Dec 16 '19 at 13:00
  • 1
    $\begingroup$ $b$ is a function so it is different for each vertex. Since $b(v) = 1$ for $v \in L$, it won't occur that one edge is used more than once. Hence, if a matching exists that saturates or the vertices on the left an algorithm for b-matching will always finds such a matching. $\endgroup$ – narek Bojikian Dec 16 '19 at 13:03
  • 1
    $\begingroup$ Yes, the problem can also be reduced to finding minimum $T$-cut which is solvable in $O(n^4)$. See Combinatorial Optimization book by Korte or by Schrijver for more details. $\endgroup$ – narek Bojikian Dec 16 '19 at 13:14
  • 1
    $\begingroup$ The problem has also min-max characterization, which means you can solve it in polynomial time as a linear program using the ellipsoid method. However, I don't think you should consider this case for a real-life implementation. (Refer to the same books) $\endgroup$ – narek Bojikian Dec 16 '19 at 13:15

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.