今が紀元前 3000 年で、異性愛規範的で一夫多妻制のスピードデートを設定していると想像してみてください。n_c男性とn_s女性がいます（ n_s > n_c）。n_rスピードデートはラウンドで進行します。各ラウンドで、男性のそれぞれが女性と会います。したがって、n_r*n_cスロットを埋める必要があります。
また、彼らはすべて、スロットの 1 つで男性と女性u(i,j)をペアにするユーティリティを提供するスコアリング関数を構築した石板アンケートに記入しました
。ij
目標は、すべてのスロットでスコアの合計を最大化することです。男性は同じ女性に 2 回以上会うことはなく、各女性は多くても男性としか会わないという制約の下で行われ
ceil(n_r*n_c/n_s)
ます。（つまり、各女性はほぼ同じ数の男性と会うべきです。）
これを解決するアルゴリズムをスケッチできますか? 男性と女性の数は 100 人未満、おそらく 50 人未満であると想定できます。ああ、現代のハードウェアを紀元前 3000 年に持ち込んだとします。
最小コストの循環問題として定式化でき、そのための多くのアルゴリズムの 1 つを使用して解決できます (たとえば、サイクル キャンセリング、ネットワーク シンプレックス。これらの多項式時間アルゴリズムは 50 要素に対して非常に高速である必要があります)。
男女それぞれの頂点を作ります。ソース/シンク頂点を作成します。男性には、ソース/シンクからのアークがあり、フローn_cと容量は最小n_cで、コストはゼロです。女性には容量のソース/シンクへのアークがありceil(n_r*n_c/n_s)、コストはゼロです。男性と女性それぞれに、男性から女性へのキャパシティ1アークがあります。このアークのコストは-u(i,j)で、男性はi、女性はjです。
今、物事をスケジュールする必要があります。このアイデアは、このラウンドをスケジュールする必要があるすべての女性に一致する男性と女性の二部マッチング (つまり、単一ラウンドのスケジュール) を繰り返し構築することです。それらは学位が男性と等しい女性です。平均化の議論 (男性の次数が k の場合、次数 k の n 人の女性が少なくとも n 人の男性の隣にいる必要があります。そうでなければ、一部の男性は k より大きい次数を持つことになります)、ホールの定理が適用され、これらの女性を完全に一致させることができます。男性に関する同様の議論により、このマッチングを繰り返し拡張して、すべての男性に一致させることができます。一致するエッジをすべて削除して繰り返します。
この論文を見つけました：
http://i11www.iti.uni-karlsruhe.de/_media/teaching/theses/sa-strasser-10.pdf
まさにこの問題を攻撃するもの。
（彼らがスピードデートの問題を実際に解決しているように見えるのは面白いです。私の定式化は、私たちが解決している実際の問題と同形のものとして作られたものです。）