すごく一般的な感じのする問題ですがパッと検索しても日本語の情報が出てこなかったので紹介します。
b-matching problem
無向グラフがあります。
枝は重みを持っています。
頂点は容量を持っています。
ここで各枝を使用するかしないか選びます。ただし各頂点について接続していてかつ使用している枝の重みの合計が容量を上回らないようにしなければなりません。
条件を満たしつつ使用している枝の重みの合計を最大化することが目的です。
参考によると多項式時間アルゴリズムが存在するみたいです。
オンライン版も研究されてるみたいですね。
参考
- Richard P.Anstee. A polynomial algorithm for b-matchings: An alternative approach. In Information Processing Letters, Volume 24, Issue 3, Pages 153-157, 1987.
-
BalaKalyanasundaram and Kirk R.Pruhs. An optimal deterministic algorithm for online b-matching. In Theoretical Computer Science, Volume 233, Issues 1–2, Pages 319-325, 2000.
