ダウンロード数: 96
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
ipsjjip.29.166.pdf | 1.26 MB | Adobe PDF | 見る/開く |
タイトル: | Hardness of Instance Generation with Optimal Solutions for the Stable Marriage Problem |
著者: | Matsuyama, Yuki Miyazaki, Shuichi https://orcid.org/0000-0003-0369-1970 (unconfirmed) |
著者名の別形: | 松山, 祐貴 宮崎, 修一 |
キーワード: | stable marriage problem NP-hardness instance generation |
発行日: | 2021 |
出版者: | Information Processing Society of Japan |
誌名: | Journal of Information Processing |
巻: | 29 |
開始ページ: | 166 |
終了ページ: | 173 |
抄録: | 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. |
著作権等: | ここに掲載した著作物の利用に関する注意 本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 |
URI: | http://hdl.handle.net/2433/261876 |
DOI(出版社版): | 10.2197/ipsjjip.29.166 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。