{"created":"2023-05-15T12:13:24.696769+00:00","links":{},"metadata":{"_buckets":{"deposit":"3168b320-6c7b-4818-a39f-845a4905bdbe"},"_deposit":{"id":"2807.1","owners":[2],"pid":{"revision_id":0,"type":"depid","value":"2807.1"},"status":"published"},"_oai":{"id":"oai:miyazaki-u.repo.nii.ac.jp:00002807.1","sets":["73","73:36","73:36:330:313"]},"author_link":["14786","11807","11805","12590"],"item_10002_alternative_title_1":{"attribute_name":"その他（別言語等）のタイトル","attribute_value_mlt":[{"subitem_alternative_title":"A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic","subitem_alternative_title_language":"en"}]},"item_10002_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2003-07","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"308","bibliographicPageStart":"303","bibliographicVolumeNumber":"32","bibliographic_titles":[{"bibliographic_title":"宮崎大学工学部紀要","bibliographic_titleLang":"ja"},{"bibliographic_title":"Memoirs of Faculty of Engineering, University of Miyazaki","bibliographic_titleLang":"en"}]}]},"item_10002_description_5":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"Abstract \nThe Lin-Kernighan (LK) heuristic is one of the most effective and efficient algorithms for the \nTraveling Salesman Problem (TSP). However, the LK heuristic is quite complicated and has many \nchoices for implementing it. Especially, the data structure for tour representation plays an important \nrole in the LK's performance. Traditionally, binary trees (including splay trees) are asymptotically \nthe best tour representation. Empirically, however, they are utilized only for solving problems with \nmore than one million cities due to the large overhead. Arrays are suitable for solving problems \nhaving up to a thousand cities and two-level trees are used for the problems with a thousand to a \nmillion cities. This paper proposes three-level trees as a new data structure. Although this structure is \nasymptotically not better than the existing ones, it perform empirically better than the existing ones \nin the range being investigated in this study (from 10(3乗) to 10(6.5乗) cities).","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_10002_publisher_8":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"宮崎大学工学部","subitem_publisher_language":"ja"},{"subitem_publisher":"Faculty of Engineering, University of Miyazaki","subitem_publisher_language":"en"}]},"item_10002_source_id_11":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA00732558","subitem_source_identifier_type":"NCID"}]},"item_10002_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"05404924","subitem_source_identifier_type":"ISSN"}]},"item_10002_version_type_20":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Nguyen, Hung Dinh","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"14786","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Yoshihara, Ikuo","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"11807","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Yamamori, Kunihito","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"11805","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"50293395","nameIdentifierScheme":"e-Rad","nameIdentifierURI":"https://kaken.nii.ac.jp/ja/search/?qm=50293395"}]},{"creatorNames":[{"creatorName":"Yasunaga, Moritoshi","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"12590","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2020-06-21"}],"displaytype":"detail","filename":"KJ00002426422.pdf","filesize":[{"value":"609.2 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"KJ00002426422.pdf","url":"https://miyazaki-u.repo.nii.ac.jp/record/2807.1/files/KJ00002426422.pdf"},"version_id":"3e298115-38dd-45d0-94fc-bc3c9783bcef"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Traveling salesman problem, Combinatorial optimization, Lin-Kernighan heuristic, Data structure, Algorithm analysis, Three-level trees","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":"departmental bulletin paper","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic","subitem_title_language":"en"}]},"item_type_id":"10002","owner":"2","path":["36","73","313"],"pubdate":{"attribute_name":"公開日","attribute_value":"2007-06-28"},"publish_date":"2007-06-28","publish_status":"0","recid":"2807.1","relation_version_is_last":true,"title":["A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic"],"weko_creator_id":"2","weko_shared_id":2},"updated":"2023-07-29T11:16:23.484089+00:00"}