| 講演名 | 2002/12/12 長さ2のタイを含む安定結婚問題に対する近似アルゴリズム 柳澤 弘揮, 宮崎 修一, 岩間 一雄, ハルダースソン マグナス, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 安定結婚問題とは,提出された希望リストに基づき,ある安定条件を満たすマッチングを求める問題である.従来の安定結婚問題では,希望リストに異性全員を全順序で記述する必要があった.タイ(同順位)を含んだ希望リストや不完全な希望リストを許すと,最大サイズの安定マッチジグを求める問題はNP困難になる.この問題に対する2-近似アルゴリズムは容易に作ることができるが,近似度が2よりも小さいアルゴリズムは知られていない.本研究では,タイの長さを2に制限した比較的自然な例題集合に対して,近似度が25/13(<1.924)の近似アルゴリズムを与えた. |
| 抄録(英) | While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, approximation of factor two is trivial. In this paper, we give a first nontrivial result for approximation of factor less than two. Our algorithm achieves a factor of 25/13(< 1.924) for a restricted case where each tie is of length two. |
| キーワード(和) | 安定結婚問題 / NP困難 / 同順位 / 不完全リスト / 近似アルゴリズム |
| キーワード(英) | the stable marriage problem / NP-hardness / ties / incomplete lists / approximation algorithms |
| 資料番号 | COMP2002-59 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/12/12(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 長さ2のタイを含む安定結婚問題に対する近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Aprroximation Algorithm for the Stable Marriage Problem with Ties of Length Two |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 安定結婚問題 / the stable marriage problem |
| キーワード(2)（和/英） | NP困難 / NP-hardness |
| キーワード(3)（和/英） | 同順位 / ties |
| キーワード(4)（和/英） | 不完全リスト / incomplete lists |
| キーワード(5)（和/英） | 近似アルゴリズム / approximation algorithms |
| 第 1 著者 氏名（和/英） | 柳澤 弘揮 / Hiroki YANAGISAWA |
| 第 1 著者 所属（和/英） | 京都大学情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 宮崎 修一 / Shuichi MIYAZAKI |
| 第 2 著者 所属（和/英） | 京都大学学術情報メディアセンター Academic Center for Computing and Media Studies, Kyoto University |
| 第 3 著者 氏名（和/英） | 岩間 一雄 / Kazuo IWAMA |
| 第 3 著者 所属（和/英） | 京都大学情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 4 著者 氏名（和/英） | ハルダースソン マグナス / Magnus HALLDORSSON |
| 第 4 著者 所属（和/英） | アイスランド大学 Science Institute, University of Iceland |
| 発表年月日 | 2002/12/12 |
| 資料番号 | COMP2002-59 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 522 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |