{"created":"2023-05-15T15:32:19.708986+00:00","id":5189,"links":{},"metadata":{"_buckets":{"deposit":"62b1af65-0fe5-460f-8eb6-efe79b92f03d"},"_deposit":{"created_by":17,"id":"5189","owners":[17],"pid":{"revision_id":0,"type":"depid","value":"5189"},"status":"published"},"_oai":{"id":"oai:barrel.repo.nii.ac.jp:00005189","sets":["1:536","4"]},"author_link":["32472","166"],"item_1_biblio_info_5":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2016-10","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"757","bibliographicPageStart":"727","bibliographicVolumeNumber":"22","bibliographic_titles":[{"bibliographic_title":"Journal of Heuristics","bibliographic_titleLang":"en"}]}]},"item_1_description_18":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"A partial Latin square (PLS) is a partial assignment of n symbols to an n x n grid such that, in each row and in each column, each symbol appears at most once. The partial Latin square extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap, i.e.,the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient (p,∞)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for p ∈ {1, 2, 3}. The runnin time of the algorithm is O(nP+1). We then propose a novel swap operation, Trellisswap,which is a generalization of (p, q)-swap with p≤2. The proposed Trellis-neighborhood search algorithm runs in O(n3·5) time. The iterated local search (ILS) algorithm with Trellisneighborhood is more likely to deliver a high-quality solution than not only ILSs with (p, ∞)neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LOCALSOLVER.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_1_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"32472","nameIdentifierScheme":"WEKO"}],"names":[{"name":"原口, 和也","nameLang":"ja"}]}]},"item_1_publisher_6":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Springer US","subitem_publisher_language":"en"}]},"item_1_relation_8":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1007/s10732-016-9317-6","subitem_relation_type_select":"DOI"}}]},"item_1_rights_13":{"attribute_name":"出版社版URI","attribute_value_mlt":[{"subitem_rights":"https://doi.org/10.1007/s10732-016-9317-6","subitem_rights_language":"ja"}]},"item_1_source_id_11":{"attribute_name":"書誌ID（NCID）","attribute_value_mlt":[{"subitem_source_identifier":"AA12120967","subitem_source_identifier_type":"NCID"}]},"item_1_source_id_7":{"attribute_name":"ISSN / EISSN","attribute_value_mlt":[{"subitem_source_identifier":"1381-1231","subitem_source_identifier_type":"PISSN"}]},"item_1_subject_16":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"007","subitem_subject_language":"ja","subitem_subject_scheme":"NDC"}]},"item_1_subject_17":{"attribute_name":"NIIサブジェクト","attribute_value_mlt":[{"subitem_subject":"情報学","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"数学","subitem_subject_language":"ja","subitem_subject_scheme":"Other"}]},"item_1_version_type_15":{"attribute_name":"テキストバージョン","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Haraguchi, Kazuya","creatorNameLang":"en","creatorNameType":"Personal"}],"nameIdentifiers":[{"nameIdentifier":"166","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-07-04"}],"displaytype":"detail","filename":"Journal of Heuristics_22_5_ pp 727–757.pdf","filesize":[{"value":"1.3 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"Journal of Heuristics_22_5_ pp 727–757","url":"https://barrel.repo.nii.ac.jp/record/5189/files/Journal of Heuristics_22_5_ pp 727–757.pdf"},"version_id":"a4a08bd0-b9c8-4ba7-8b26-b47aba8b60f4"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem","subitem_title_language":"en"}]},"item_type_id":"1","owner":"17","path":["4","536"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2018-07-04"},"publish_date":"2018-07-04","publish_status":"0","recid":"5189","relation_version_is_last":true,"title":["Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem"],"weko_creator_id":"17","weko_shared_id":-1},"updated":"2025-03-17T00:38:51.741354+00:00"}