文献

J-GLOBAL ID：202002210914456896   整理番号：20A2077907

半積分の場合におけるTSPのための改良近似アルゴリズム【JST・京大機械翻訳】

An improved approximation algorithm for TSP in the half integral case

著者 (3件)： Karlin Anna R. (University of Washington, USA) ,  Klein Nathan (University of Washington, USA) ,  Gharan Shayan Oveis (University of Washington, USA)
資料名： ACM Proceedings  (ACM Proceedings)
号： STOC 2020  ページ： 28-39  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： サブトゥー線形プログラミング緩和に対する最適解が半積分である事例に対して,計量巡回セールス問題(TSP)のための1.4993近似アルゴリズムを設計した。これらの事例は,半積分LP解がすべての分数解に対して最大の積分ギャップを持つ,Schalekamp,Williamsonおよびvan Zuylenスタチンの予想により,過去10年間にわたって大きな注目を受けた。したがって,Schalekampらの予想が真実であるならば,著者らの結果は,サブトゥーポリトープの積分ギャップが3/2から離れていることを示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 線形計画法 ,  *緩和現象
準シソーラス用語： 最適解 ,  *近似アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (6件)： 近似アルゴリズム ,  サボテン表現 ,  最大エントロピー ,  ランダム丸め ,  強Rayleigh ,  巡回セールスマン問題

分類 (1件)： ネットワーク法  (KA03040X)

タイトルに関連する用語 (2件)： 積分 ,  近似アルゴリズム