ダウンロード数: 278
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
transinf_E89-D_2380.pdf | 225.27 kB | Adobe PDF | 見る/開く |
タイトル: | A (2-c log N/N)-Approximation Algorithm for the Stable Marriage Problem |
著者: | Iwama, Kazuo Miyazaki, Shuichi https://orcid.org/0000-0003-0369-1970 (unconfirmed) Okamoto, Kazuya https://orcid.org/0000-0002-9079-2253 (unconfirmed) |
著者名の別形: | 岩間, 一雄 宮崎, 修一 岡本, 和也 |
キーワード: | stable marriage problem incomplete lists ties approximation algorithms local search |
発行日: | 1-Aug-2006 |
出版者: | Institute of Electronics, Information and Communications Engineers (IEICE) |
誌名: | IEICE TRANSACTIONS on Information and Systems |
巻: | E89-D |
号: | 8 |
開始ページ: | 2380 |
終了ページ: | 2387 |
抄録: | An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both 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, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio A [2-c log N/N] for an arbitrarily positive constant c, where N denotes the number of men in an input. |
著作権等: | © 2006 The Institute of Electronics, Information and Communication Engineers |
URI: | http://hdl.handle.net/2433/227018 |
関連リンク: | http://search.ieice.org/bin/summary.php?id=e89-d_8_2380&category=D&year=2006&lang=E&abst= |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。