{"created":"2025-01-19T01:11:32.835100+00:00","updated":"2025-01-19T18:11:59.946307+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00210293","sets":["1164:2592:10486:10558"]},"path":["10558"],"owner":"44499","recid":"210293","title":["A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-03-10"},"_buckets":{"deposit":"aad8de2f-5085-4dd1-8ee4-f7bf7794cdd8"},"_deposit":{"id":"210293","pid":{"type":"depid","value":"210293","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem","author_link":["531928","531929","531927","531926"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem"},{"subitem_title":"A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2021-03-10","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Research Institute for Mathematical Sciences, Kyoto University"},{"subitem_text_value":"Research Institute for Mathematical Sciences, Kyoto University"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Research Institute for Mathematical Sciences, Kyoto University","subitem_text_language":"en"},{"subitem_text_value":"Research Institute for Mathematical Sciences, Kyoto University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/210293/files/IPSJ-AL21182012.pdf","label":"IPSJ-AL21182012.pdf"},"date":[{"dateType":"Available","dateValue":"2023-03-10"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL21182012.pdf","filesize":[{"value":"704.7 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"be87dc1b-ffd4-4260-98d8-b13957a0200e","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2021 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yuki, Amano"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuhisa, Makino"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yuki, Amano","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazuhisa, Makino","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"In this paper, we consider differential approximability of the traveling salesman problem (TSP). The differential approximation ratio was proposed by Demange and Paschos in 1996 as an approximation criterion that is invariant under affine transformation of the objective function. We show that TSP is 3/4-differential approximable, which improves the currently best known bound 3/4 - O(1/n) due to Escoffier and Monnot in 2008, where n denotes the number of vertices in the given graph.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"In this paper, we consider differential approximability of the traveling salesman problem (TSP). The differential approximation ratio was proposed by Demange and Paschos in 1996 as an approximation criterion that is invariant under affine transformation of the objective function. We show that TSP is 3/4-differential approximable, which improves the currently best known bound 3/4 - O(1/n) due to Escoffier and Monnot in 2008, where n denotes the number of vertices in the given graph.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"7","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2021-03-10","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"12","bibliographicVolumeNumber":"2021-AL-182"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":210293,"links":{}}