WEKO3
アイテム
{"_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": ["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", "download_preview_message": "", "file_order": 0, "filename": "LNCS-2015-8496.pdf", "filesize": [{"value": "198.2 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 198200.0, "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"], "permalink_uri": "http://hdl.handle.net/10252/00005670", "pubdate": {"attribute_name": "公開日", "attribute_value": "2017-06-19"}, "publish_date": "2017-06-19", "publish_status": "0", "recid": "5044", "relation": {}, "relation_version_is_last": true, "title": ["An Efficient Local Search for Partial Latin Square Extension Problem"], "weko_shared_id": 3}
An Efficient Local Search for Partial Latin Square Extension Problem
http://hdl.handle.net/10252/00005670
http://hdl.handle.net/10252/00005670218d89d7-e2e4-495b-a105-a0c660e08387
名前 / ファイル | ライセンス | アクション |
---|---|---|
LNCS-2015-8496.pdf (198.2 kB)
|
|
Item type | 学術雑誌論文 / Journal Article_default(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2017-06-19 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | An Efficient Local Search for Partial Latin Square Extension Problem | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | partial Latin square extension problem | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | maximum independent set problem | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | metaheuristics | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | local search | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
資源タイプ | journal article | |||||
著者 |
Haraguchi, Kazuya
× Haraguchi, Kazuya |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | 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. | |||||
書誌情報 |
en : Lecture Notes in Computer Science 巻 9075, p. 182-198, 発行日 2015-04-16 |
|||||
出版者 | ||||||
出版者 | Springer International Publishing | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 0302-9743 | |||||
DOI | ||||||
関連タイプ | isVersionOf | |||||
識別子タイプ | DOI | |||||
関連識別子 | 10.1007/978-3-319-18008-3_13 | |||||
権利 | ||||||
権利情報 | The original publication is available at www.springerlink.com | |||||
関連サイト | ||||||
識別子タイプ | URI | |||||
関連識別子 | https://link.springer.com/chapter/10.1007/978-3-319-18008-3_13 | |||||
著者版フラグ | ||||||
出版タイプ | AM | |||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
日本十進分類法 | ||||||
主題Scheme | NDC | |||||
主題 | 007 |