{"created":"2023-05-15T15:32:13.107416+00:00","id":5044,"links":{},"metadata":{"_buckets":{"deposit":"b6bd45e7-79d6-4191-b8bf-b836313aea4b"},"_deposit":{"created_by":3,"id":"5044","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"5044"},"status":"published"},"_oai":{"id":"oai:barrel.repo.nii.ac.jp:00005044","sets":["1:536"]},"author_link":["9986"],"item_10001_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2015-04-16","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"198","bibliographicPageStart":"182","bibliographicVolumeNumber":"9075","bibliographic_titles":[{},{"bibliographic_title":"Lecture Notes in Computer Science","bibliographic_titleLang":"en"}]}]},"item_10001_description_5":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"A partial Latin square (PLS) is a partial assignment of nsymbols to an n×n grid such that, in each row and in each column, eachsymbol appears at most once. The partial Latin square extension problemis an NP-hard problem that asks for a largest extension of a givenPLS. In this paper we propose an efficient local search for this problem.We focus on the local search such that the neighborhood is defined by(p, q)-swap, i.e., removing exactly p symbols and then assigning symbolsto at most qempty cells. For p ∈ {1, 2, 3}, our neighborhood search algorithmfinds an improved solution or concludes that no such solutionexists in O(np+1) time. We also propose a novel swap operation,Trellisswap,which is a generalization of (1, q)-swap and (2, q)-swap. Our Trellisneighborhoodsearch algorithm takes O(n3.5) time to do the same thing.Using these neighborhood search algorithms, we design a prototype iteratedlocal search algorithm and show its effectiveness in comparisonwith state-of-the-artoptimization solvers such as IBM ILOG CPLEX and LocalSolver.","subitem_description_type":"Abstract"}]},"item_10001_publisher_8":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Springer International Publishing"}]},"item_10001_relation_14":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"10.1007/978-3-319-18008-3_13","subitem_relation_type_select":"DOI"}}]},"item_10001_relation_17":{"attribute_name":"関連サイト","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://link.springer.com/chapter/10.1007/978-3-319-18008-3_13","subitem_relation_type_select":"URI"}}]},"item_10001_rights_15":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"The original publication is available at www.springerlink.com"}]},"item_10001_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0302-9743","subitem_source_identifier_type":"ISSN"}]},"item_10001_subject_21":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"007","subitem_subject_scheme":"NDC"}]},"item_10001_version_type_20":{"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"}],"nameIdentifiers":[{"nameIdentifier":"9986","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-06-19"}],"displaytype":"detail","filename":"LNCS-2015-8496.pdf","filesize":[{"value":"198.2 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"LNCS-2015-8496.pdf ","url":"https://barrel.repo.nii.ac.jp/record/5044/files/LNCS-2015-8496.pdf"},"version_id":"365a7868-1dec-4f1b-9bdf-b622db26dd72"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"partial Latin square extension problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"maximum independent set problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"metaheuristics","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"local search","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"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":"An Efficient Local Search for Partial Latin Square Extension Problem","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"An Efficient Local Search for Partial Latin Square Extension Problem","subitem_title_language":"en"}]},"item_type_id":"10001","owner":"3","path":["536"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-06-19"},"publish_date":"2017-06-19","publish_status":"0","recid":"5044","relation_version_is_last":true,"title":["An Efficient Local Search for Partial Latin Square Extension Problem"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-05-15T15:51:51.921872+00:00"}