MANY-TO-MANY STABLE MATCHINGS WITH TIES IN TREES

• Nakamura Keita

  Kyushu University

• Kamiyama Naoyuki

  Kyushu University

抄録

In the stable matching problem introduced by Gale and Shapley, it is known that in the case where the preference lists may involve ties, a stable matching always exists, but the sizes of stable matchings may be different. In this paper, we consider the problem of finding a maximum-size stable matching in a many-to-many matching market with ties. It is known that this problem is NP-hard even if the capacity of every agent is one. In this paper, we prove that this problem in trees can be solved in polynomial time by extending the algorithm proposed by Tayu and Ueno for the one-to-one setting.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 59 (3), 225-240, 2016

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Discrete optimization
• stable matching
• tree
• tie

詳細情報

• CRID: 1390001204109083776
• NII論文ID: 130005163068
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.59.225
• ISSN: 21888299
• ISSN: 04534514
• NDL書誌ID: 027463094
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I027463094
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/59/3/59_225/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可