ダウンロード数: 164
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
IEICE_tec.rep_COMP2007-41.pdf | 2.13 MB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | 岡本, 和也 | ja |
dc.contributor.author | 宮崎, 修一 | ja |
dc.contributor.author | 岩間, 一雄 | ja |
dc.contributor.alternative | Okamoto, Kazuya | en |
dc.contributor.alternative | Miyazaki, Shuichi | en |
dc.contributor.alternative | Iwama, Kazuo | en |
dc.contributor.transcription | オカモト, カズヤ | - |
dc.contributor.transcription | ミヤザキ, シュウイチ | - |
dc.contributor.transcription | イワマ, カズオ | - |
dc.date.accessioned | 2017-09-07T01:35:13Z | - |
dc.date.available | 2017-09-07T01:35:13Z | - |
dc.date.issued | 2007-10-09 | - |
dc.identifier.issn | 0913-5685 | - |
dc.identifier.uri | http://hdl.handle.net/2433/227008 | - |
dc.description | <コンピュテーション研究会(COMP)> 2007年10月16日(火) 10:40 - 16:40, 東北大学工学部電子情報システム・応物系1号館451・453号室 | ja |
dc.description.abstract | 安定ルームメイト問題は, 希望リストに基づいて「安定性」を満たすように, 2N人の人間をN組のペアに分割する問題である.安定ルームメイト問題は解を持たない場合もあるが, 解を持つか否かを判定し, 持つ場合には解を見つける多項式時間アルゴリズムが知られている.本研究ではこの問題を拡張し, 3N人の人間をN組のトリプルに分割する問題を提案する.そして, この問題において解の存在を判定する問題がNP完全であることを示す. | ja |
dc.description.abstract | 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. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | jpn | - |
dc.publisher | 電子情報通信学会 | ja |
dc.publisher.alternative | Institute of Electronics, Information and Communication Engineers (IEICE) | en |
dc.rights | © 電子情報通信学会(IEICE) | ja |
dc.subject | 安定マッチング | ja |
dc.subject | 安定ルームメイト問題 | ja |
dc.subject | NP完全 | ja |
dc.subject | stable matching | en |
dc.subject | the stable roommates problem | en |
dc.subject | NP-complete | en |
dc.title | 3人部屋安定ルームメイト問題のNP完全性 | ja |
dc.title.alternative | NP-Completeness of the Stable Roommates Problem with Triple Rooms | en |
dc.type | research report | - |
dc.type.niitype | Research Paper | - |
dc.identifier.ncid | AN10013152 | - |
dc.identifier.jtitle | 電子情報通信学会技術研究報告 | ja |
dc.identifier.volume | 107 | - |
dc.identifier.issue | 258 | - |
dc.identifier.spage | 1 | - |
dc.identifier.epage | 6 | - |
dc.textversion | publisher | - |
dc.identifier.artnum | COMP2007-41 | - |
dc.address | 京都大学 | ja |
dc.address | 京都大学 | ja |
dc.address | 京都大学 | ja |
dc.address.alternative | Kyoto University | en |
dc.address.alternative | Kyoto University | en |
dc.address.alternative | Kyoto University | en |
dc.relation.url | http://www.ieice.org/ken/paper/20071016fAyh/ | - |
dc.relation.NAID | 110006456717 | - |
dcterms.accessRights | open access | - |
dc.identifier.jtitle-alternative | IEICE technical report : 信学技報 | en |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。