Hardness of Instance Generation with Optimal Solutions for the Stable Marriage Problem

• Matsuyama Yuki

  Graduate School of Informatics, Kyoto University

• Miyazaki Shuichi

  Academic Center for Computing and Media Studies, Kyoto University

抄録

In a variant of the stable marriage problem where ties and incomplete lists are allowed, finding a stable matching of maximum cardinality is known to be NP-hard. There are a lot of experimental studies for evaluating the performance of approximation algorithms or heuristics, using randomly generated or artificial instances. One of standard evaluation methods is to compare an algorithm's solution with an optimal solution, but finding an optimal solution itself is already hard. In this paper, we investigate the possibility of generating instances with known optimal solutions. We propose three instance generators based on a known random generation algorithm, but unfortunately show that none of them meet our requirements, implying a difficulty of instance generation in this approach.

収録刊行物

• Journal of Information Processing

  Journal of Information Processing 29 (0), 166-173, 2021

  一般社団法人 情報処理学会

キーワード

• stable marriage problem
• NP-hardness
• instance generation

詳細情報

• CRID: 1390568617219929216
• NII論文ID: 120006979748
• NII論文ID: 130007986874
• DOI: 10.2197/ipsjjip.29.166
• ISSN: 18826652
• HANDLE: 2433/261876
• Web Site: https://www.jstage.jst.go.jp/article/ipsjjip/29/0/29_166/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可