労働者嗜好に基づいてチームに労働者を割り当てるアルゴリズム

Question

労働者はNで、Mチームの1人に割り当てる必要があります。各チームは、最大でK人の労働者を持つことができます。各作業者は、最も優先度の高いチームの場合は1から、優先度の低いチームの場合はMに、優先度の順にチームをランク付けします。問題はマッチングを見つけることで、各チームが最大でK人の労働者を持つことができるという条件で、最も好むチームで作業を終えることができます。

最初は私が考えていたが、これはHungarian Algorithmを使用して解決できるAssignment problemだと思った。しかし、ハンガリーのアルゴリズムは、各作業者が正確に1つのアイテムに割り当てられている場合にのみ使用できることを認識しました。しかし、私の場合、複数の労働者を同じチームに割り当てることができます。

今、私はこれが本当にどんな種類の問題であるか確信しています。これは（複数の）Knapsack problemですか、Bin packing problemですか？どのような種類のアルゴリズムを使って問題を解決できますか？そして、あなたがチームに各ワーカーを割り当てる必要がありますし、各チームが唯一することができます - あなたは1の容量を持つKのチームに各チームが重複した場合は

は：小さな調整で

Answer 1

この問題に対処するには2通りの方法があります。どれだけ多くの人数とチーム数があり、どのくらい大きいかによって効率的です。Kです。

（@Alex L.の答えですでに述べられている）より簡単な方法は、各チームをKチームに分割し、問題をハンガリーのアルゴリズムで解決できる通常の重み付き二者間マッチングに変換することです。今、ハンガリーのアルゴリズムの複雑さはO(n^2 * m)です。ここでは、人数をn、チーム数をmとします。各チームをkに分割した後、最終的な複雑さはO(n^2 * m * k)になります。

もう1つの方法は、この問題を最小コスト最大フロー問題として扱うことです。ソースとシンクが2つの余分なノードであるグラフを構築すると、ソースに直接接続されたすべての作業者が容量1と重量0を持ち、すべてのチームが容量kと体重が0のシンクに接続し、 1とその嗜好に応じた費用が含まれます。最小コスト最大流量は複雑さがO(n^3 * m)です。ここで、nとなるチーム数をmとすると、ハンガリー人よりも厳密に悪いものが得られます（おそらくk < nなので）。しかし、nをチーム数、mを労働者数とすると、労働者数が多く、チーム数が少なく、kも大きい場合、潜在的にハンガリーよりも優れたものになる可能性があります。

あなたの制約によります。 mがkおよびnよりも大幅に小さい場合は、最小コストの最大流量でより効果的です。そうでない場合はチームをkに分割し、バニラハンガリーアルゴリズムを使用します。

Answer 2

、それが割り当て問題になることができます1人の作業員に割り当てられます。

割り当て問題では、エージェントとタスクの数が等しくなくてもかまいません。