Downloads: 42

Files in This Item:
File Description SizeFormat 
ipsjjip.29.166.pdf1.26 MBAdobe PDFView/Open
Title: Hardness of Instance Generation with Optimal Solutions for the Stable Marriage Problem
Authors: Matsuyama, Yuki
Miyazaki, Shuichi  kyouindb  KAKEN_id  orcid https://orcid.org/0000-0003-0369-1970 (unconfirmed)
Author's alias: 松山, 祐貴
宮崎, 修一
Keywords: stable marriage problem
NP-hardness
instance generation
Issue Date: 2021
Publisher: Information Processing Society of Japan
Journal title: Journal of Information Processing
Volume: 29
Start page: 166
End page: 173
Abstract: 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.
Rights: ここに掲載した著作物の利用に関する注意 本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
URI: http://hdl.handle.net/2433/261876
DOI(Published Version): 10.2197/ipsjjip.29.166
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.