1. Kyoto University Research Information Repository
  2. 630_Academic Center for Computing and Media Studies
  3. Journal Articles
Downloads: 543

    Please use this identifier to cite or link to this item: http://hdl.handle.net/2433/226941
Files in This Item:
File Description SizeFormat 
s00453-012-9699-2.pdf139.98 kBAdobe PDFView/Open
Full metadata record
DC FieldValueLanguage
dc.contributor.authorIwama, Kazuoen
dc.contributor.authorMiyazaki, Shuichien
dc.contributor.authorYanagisawa, Hirokien
dc.contributor.alternative岩間, 一雄ja
dc.contributor.alternative宮崎, 修一ja
dc.contributor.alternative柳澤, 弘揮ja
dc.date.accessioned2017-08-31T02:03:35Z-
dc.date.available2017-08-31T02:03:35Z-
dc.date.issued2014-03-
dc.identifier.issn0178-4617-
dc.identifier.urihttp://hdl.handle.net/2433/226941-
dc.description.abstractThe 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).en
dc.format.mimetypeapplication/pdf-
dc.language.isoeng-
dc.publisherSpringer USen
dc.rightsThe final publication is available at Springer via https://doi.org/10.1007/s00453-012-9699-2en
dc.rightsThe 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'.en
dc.rightsThis is not the published version. Please cite only the published version.en
dc.rightsこの論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。ja
dc.subjectThe stable marriage problemen
dc.subjectThe stable marriage with ties and incomplete listsen
dc.subjectApproximation algorithmen
dc.subjectInteger programen
dc.subjectLinear program relaxationen
dc.subjectIntegrality gapen
dc.titleA 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Tiesen
dc.typejournal article-
dc.type.niitypeJournal Article-
dc.identifier.jtitleAlgorithmicaen
dc.identifier.volume68-
dc.identifier.issue3-
dc.identifier.spage758-
dc.identifier.epage775-
dc.relation.doi10.1007/s00453-012-9699-2-
dc.textversionauthor-
dc.addressGraduate School of Informatics, Kyoto Universityen
dc.addressAcademic Center for Computing and Media Studies, Kyoto Universityen
dc.addressIBM Research—Tokyoen
dcterms.accessRightsopen access-
datacite.date.available2015-03-01-
datacite.awardNumber22240001-
datacite.awardNumber20700009-
datacite.awardNumber24500013-
jpcoar.funderName日本学術振興会ja
jpcoar.funderName日本学術振興会ja
jpcoar.funderName日本学術振興会ja
jpcoar.funderName.alternativeJapan Society for the Promotion of Science (JSPS)en
jpcoar.funderName.alternativeJapan Society for the Promotion of Science (JSPS)en
jpcoar.funderName.alternativeJapan Society for the Promotion of Science (JSPS)en
Appears in Collections:Journal Articles

Show simple item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.