ダウンロード数: 161
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
IEICE_tec.rep_COMP2009-37.pdf | 2.22 MB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | 濱田, 浩気 | ja |
dc.contributor.author | 宮崎, 修一 | ja |
dc.contributor.author | 岩間, 一雄 | ja |
dc.contributor.alternative | Hamada, Koki | 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:34:14Z | - |
dc.date.available | 2017-09-07T01:34:14Z | - |
dc.date.issued | 2009-10-09 | - |
dc.identifier.issn | 0913-5685 | - |
dc.identifier.uri | http://hdl.handle.net/2433/227006 | - |
dc.description | <コンピュテーション研究会(COMP)> 2009年10月16日(金) 10:00 - 16:35, 東北大学 青葉山キャンパス 電子情報システム・応物系 南講義棟103講義室 | ja |
dc.description.abstract | 安定結婚問題で不完全希望リストを許すと, 同じ例題に対する全ての安定マッチングは同サイズになる.しかし, 安定性を無視すると, 一般にはそれよりも大きなサイズのマッチングが存在する.Biroらは, 最大サイズのマッチングの中で出来るだけブロッキングペア数の少ないマッチングを求める問題を提案した.彼らは, (i)この問題がNP困難であり, 任意の正定数εに対してP≠NPの仮定の下でn^<1-ε>-近似アルゴリズムを持たないこと(nは例題中の男性の数), (ii)希望リストの長さを3以下に制限してもNP困難であり, ある定数δ>1が存在しP≠NPの仮定の下でδ-近似アルゴリズムを持たないこと, (iii)片側の性(例えば男性)の希望リストの長さが全て2以下ならば多項式時間で解けること, を示した.本論文では, 上記(ii)の近似不可能性を, 定数δからn^<1-ε>(εは任意の正定数)へと改良した. | ja |
dc.description.abstract | In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biro et al. defined the problem of finding a maximum cardinality matching that contains minimum number of blocking pairs. They proved that (i) this problem is NP-hard and cannot be approximated within the ratio of n^<1-ε> for any constant ε>0 unless P=NP, where n is the number of men in an input, (ii) even if each preference list is of length at most 3, the problem remains NP-hard and there exists a constant δ(>1) such that this problem cannot be approximated within the ratio of δ unless P=NP, and (iii) if the length of preference lists of one sex is at most 2, this problem is solvable in polynomial time. In this paper, we improve the constant δ of (ii) to n^<1-ε> for any ε>0. | 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 | ©2009 by IEICE | en |
dc.subject | 安定結婚問題 | ja |
dc.subject | 近似アルゴリズム | ja |
dc.subject | 近似度 | ja |
dc.subject | 多項式時間変換 | ja |
dc.subject | the stable marriage problem | en |
dc.subject | approximation algorithms | en |
dc.subject | approximation ratio | en |
dc.subject | polynomial-time reduction | en |
dc.title | 最大サイズ最大安定度マッチング問題に対する近似下限の改良 | ja |
dc.title.alternative | An Improved Approximation Lower Bound for Maximum Cardinality Almost Stable Matching Problem | en |
dc.type | research report | - |
dc.type.niitype | Research Paper | - |
dc.identifier.ncid | AN10013152 | - |
dc.identifier.jtitle | 電子情報通信学会技術研究報告 | ja |
dc.identifier.volume | 109 | - |
dc.identifier.issue | 235 | - |
dc.identifier.spage | 35 | - |
dc.identifier.epage | 40 | - |
dc.textversion | publisher | - |
dc.identifier.artnum | COMP2009-37 | - |
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/20091016xaQr/ | - |
dc.relation.NAID | 110007483106 | - |
dcterms.accessRights | open access | - |
dc.identifier.jtitle-alternative | IEICE technical report : 信学技報 | en |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。