ダウンロード数: 475
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| s00453-012-9699-2.pdf | 139.98 kB | Adobe PDF | 見る/開く |
| タイトル: | A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties |
| 著者: | Iwama, Kazuo Miyazaki, Shuichi   https://orcid.org/0000-0003-0369-1970 (unconfirmed)Yanagisawa, Hiroki |
| 著者名の別形: | 岩間, 一雄 宮崎, 修一 柳澤, 弘揮 |
| キーワード: | The stable marriage problem The stable marriage with ties and incomplete lists Approximation algorithm Integer program Linear program relaxation Integrality gap |
| 発行日: | Mar-2014 |
| 出版者: | Springer US |
| 誌名: | Algorithmica |
| 巻: | 68 |
| 号: | 3 |
| 開始ページ: | 758 |
| 終了ページ: | 775 |
| 抄録: | The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (>1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (>1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (<1.4706). |
| 著作権等: | The final publication is available at Springer via https://doi.org/10.1007/s00453-012-9699-2 The full-text file will be made open to the public on 01 March 2015 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
| URI: | http://hdl.handle.net/2433/226941 |
| DOI(出版社版): | 10.1007/s00453-012-9699-2 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。