是否存在諸如使用不同b值進行b匹配的問題?


0

考慮兩人的Garph $ G =(L \ cup R,E)$ 。自然,b匹配問題是找到一組邊 $ M \ subset E $ ,這樣,$ L $ $ R $ 與最大的 $ b $ 鄰居相鄰,並且權重函數 $ w(e),e \ in E $ 被最大化。如果我們有不同的 $ b $ 怎麼辦?例如, $ b(v)= 5,\ forall v \ in R $ $ b(v)= 2,\ forall v \ in L $ 。你怎麼稱呼這個問題?是約束匹配,還是k基數分配,還是什麼?我需要找到一些文獻。

謝謝!

0

I'm not sure if it's a standard problem, but it seems this problem is described in Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking.

(the other closest things I found are https://en.wikipedia.org/wiki/Generalized_assignment_problem and https://link.springer.com/content/pdf/10.1007/BF02190106.pdf, but they are talking about one-to-many assignments).

Anyway, you can solve it using maximum flow. For $b=1$ (usual matching) you can check these slides, namely this picture: enter image description here

I.e. we create auxiliary vertices $s$ and $t$, create edges $(s, u)$ for all $u$ in the left part and $(v, t)$ for all $v$ in the right part. All edges have capacity one. By solving maximum flow on this graph, you'll find maximum matching (Note: you have to find an integral solution, i.e. where flow through each edge is either 1 or 0, but standard maximum flow algorithms will do that).

For $b>1$ the graph is the same. The difference is that all edges $(s,u)$ have capacity $b_L$ and $(v,t)$ have capacity $b_R$.

If your edges have weights, then you can negate edge weights and solve min-cost max-flow on this graph.