Access count of this item: 138
|Title:||A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties|
|Author's alias:||岩間, 一雄|
|Keywords:||The stable marriage problem|
The stable marriage with ties and incomplete lists
Linear program relaxation
|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. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
|Appears in Collections:||Journal Articles|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.