1. Kyoto University Research Information Repository
  2. 630　学術情報メディアセンター
  3. 学術雑誌掲載論文等
ダウンロード数: 441

    このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/2433/226941
このアイテムのファイル:
ファイル 記述 サイズフォーマット 
s00453-012-9699-2.pdf139.98 kBAdobe PDF見る/開く
完全メタデータレコード
DCフィールド値言語
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
出現コレクション:学術雑誌掲載論文等

アイテムの簡略レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。