Downloads: 155

Files in This Item:
File Description SizeFormat 
IEICE_tec.rep_COMP2007-41.pdf2.13 MBAdobe PDFView/Open
Title: 3人部屋安定ルームメイト問題のNP完全性
Other Titles: NP-Completeness of the Stable Roommates Problem with Triple Rooms
Authors: 岡本, 和也  KAKEN_name
宮崎, 修一  KAKEN_id  orcid (unconfirmed)
岩間, 一雄  KAKEN_name
Author's alias: Okamoto, Kazuya
Miyazaki, Shuichi
Iwama, Kazuo
Keywords: 安定マッチング
stable matching
the stable roommates problem
Issue Date: 9-Oct-2007
Publisher: 電子情報通信学会
Journal title: 電子情報通信学会技術研究報告
Volume: 107
Issue: 258
Start page: 1
End page: 6
Thesis number: COMP2007-41
Abstract: 安定ルームメイト問題は, 希望リストに基づいて「安定性」を満たすように, 2N人の人間をN組のペアに分割する問題である.安定ルームメイト問題は解を持たない場合もあるが, 解を持つか否かを判定し, 持つ場合には解を見つける多項式時間アルゴリズムが知られている.本研究ではこの問題を拡張し, 3N人の人間をN組のトリプルに分割する問題を提案する.そして, この問題において解の存在を判定する問題がNP完全であることを示す.
In the stable roommates problem, we are given 2N people, each having a preference list that ranks remaining 2N-1 people in a strict order according to his/her preferences. It asks to find a stable matching, namely, a set of N pairs that satisfies the "stability" condition. There are instances that have no solution, but Irving has developed a polynomial time algorithm that decides if there exists a solution, and finds one if exists. We extend this problem into 3-dimension. In our problem, we are given 3N people and are asked to partition them into N triples. We prove that the problem of deciding if a stable matching exists is NP-complete.
Description: <コンピュテーション研究会(COMP)> 2007年10月16日(火) 10:40 - 16:40, 東北大学工学部電子情報システム・応物系1号館451・453号室
Rights: © 電子情報通信学会(IEICE)
Related Link:
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks

Export Format: 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.