【2022年1月締切】CiNii ArticlesへのCiNii Researchへの統合に伴う機関認証の移行確認について

【1/6更新】2022年4月1日からのCiNii ArticlesのCiNii Researchへの統合について

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

この論文をさがす

抄録

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.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.29(2021) (online)DOI http://dx.doi.org/10.2197/ipsjjip.29.166------------------------------

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.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.29(2021) (online)DOI http://dx.doi.org/10.2197/ipsjjip.29.166------------------------------

収録刊行物

被引用文献 (0)*注記

もっと見る

参考文献 (0)*注記

もっと見る

関連論文

もっと見る

関連研究データ

もっと見る

関連図書・雑誌

もっと見る

関連博士論文

もっと見る

関連プロジェクト

もっと見る

関連その他成果物

もっと見る

詳細情報

ページトップへ