条件を緩和した安定結婚問題の複雑さ

スポンサーリンク

概要

論文の詳細を見る
安定結婚問題とは, N人ずつの男女と各個人が異性に対する好みの順を書いた希望リストが与えられたときに, 安定なN組のペアを求める問題である。本問題に対しては多項式時間アルゴリズムが存在することが知られている。また, この問題の希望リストに対する条件の緩和として, 異性全員を書かなくてもよい場合や, 異性の希望順位に同順位を許す場合などが考えられるが, これらの緩和を単独で用いた場合にも, 解の存在を判定する多項式時間アルゴリズムが知られている。本稿ではこれらの緩和を同時に行った場合に問題がNP完全になることを示す。また, 本問題にコストを導入した最適化問題に対して, 近似度の良いアルゴリズムが存在しないことを示す。
一般社団法人情報処理学会の論文
1999-03-15

著者

関連論文

もっと見る

スポンサーリンク