Downloads: 520
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| s00453-012-9699-2.pdf | 139.98 kB | Adobe PDF | View/Open |
| Title: | A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties |
| Authors: | Iwama, Kazuo Miyazaki, Shuichi   https://orcid.org/0000-0003-0369-1970 (unconfirmed)Yanagisawa, Hiroki |
| Author's alias: | 岩間, 一雄 宮崎, 修一 柳澤, 弘揮 |
| Keywords: | The stable marriage problem The stable marriage with ties and incomplete lists Approximation algorithm Integer program Linear program relaxation Integrality gap |
| Issue Date: | Mar-2014 |
| Publisher: | Springer US |
| Journal title: | Algorithmica |
| Volume: | 68 |
| Issue: | 3 |
| Start page: | 758 |
| End page: | 775 |
| Abstract: | 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). |
| Rights: | 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(Published Version): | 10.1007/s00453-012-9699-2 |
| Appears in Collections: | Journal Articles |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.