研究

b-matching problem(bマッチング問題)とは

すごく一般的な感じのする問題ですがパッと検索しても日本語の情報が出てこなかったので紹介します。

b-matching problem

無向グラフがあります。

枝は重みを持っています。

頂点は容量を持っています。

ここで各枝を使用するかしないか選びます。ただし各頂点について接続していてかつ使用している枝の重みの合計が容量を上回らないようにしなければなりません。

条件を満たしつつ使用している枝の重みの合計を最大化することが目的です。

参考によると多項式時間アルゴリズムが存在するみたいです。

オンライン版も研究されてるみたいですね。

参考