安定結婚問題における最大最適選好マッチングの頂点集合の一意性
この論文をさがす
抄録
本稿では安定結婚問題における最適選好マッチングの解構造ついて考える.安定結婚問題の入力は,男性集合と女性集合および各人の選好順序からなる.本稿では,男性の人数と女性の人数が異なる場合を許し,選好順序は全順序制約を満たす不完全リストとする.最適選好マッチングとは,あるマッチングMよりも多くの人々に好まれるマッチングM′が存在しないようなマッチングMのことであり,安定マッチングの緩和概念として知られる.本稿では,特に最適選好マッチングのサイズに着目した議論を行う.具体的には,最大最適選好マッチングを構成する男女はマッチングによらず一意であることを示す.また最適選好マッチングを構成する頂点集合の包含関係に関する半順序構造について考察する.
収録刊行物
-
- 情報処理学会研究報告. AL, アルゴリズム研究会報告
-
情報処理学会研究報告. AL, アルゴリズム研究会報告 2013 (19), 1-4, 2013-05-10
一般社団法人情報処理学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1571417127893890048
-
- NII論文ID
- 110009579695
-
- NII書誌ID
- AN1009593X
-
- ISSN
- 09196072
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles