b-matchingというものを知った。
グラフ
が与えられたとき、次の条件を満たす辺集合
はb-matchingであるという。
各頂点のdegree restrictionを
とし、各辺のcapacity 
が与えられる。このとき各辺についてcapacity以下の重みをとって、各頂点について隣接する辺の重みの和がdegree constraints以下になるとき、この重みのとり方はb-matchingであるという。
とくに、
とすると通常のマッチングである。各辺の価値
と各辺の重みの積の和を最大化するとき、maximum weight capaciteted b-matchingという。多項式時間アルゴリズムが存在する。
https://www.di.ens.fr/~cchuang/work/small_weight.pdf
