抄録
A-024
配属人数下限付き研究室配属問題
◎上田　俊・岩崎　敦・横尾　真（九大）
本論文では下限付き研究室配属問題のための多項式時間アルゴリズムを提案する．研究室配属問題は複数の学生を一つの研究室に割り当てる多対一マッチング問題として扱われている．一方で教員の負担の均等化などの理由から割当人数の下限が重要となる．しかし，下限を考慮するとき，従来優れているとされてきたGale-Shapley algorithmをそのまま適用できないことが知られている．これに対して提案アルゴリズムは，下限付き研究室配属問題に対して，(a) 正当と認められる不満を持つ学生が存在しない，(b) 学生側の戦略的操作不可能性を満足するといった性質を満たす．