文献

J-GLOBAL ID：201902210480125489   整理番号：19A1541590

非対称巡回セールスマン経路Lpは一定積分率を持つ【JST・京大機械翻訳】

The Asymmetric Traveling Salesman Path LP Has Constant Integrality Ratio

著者 (3件)： Kohne Anna (Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany) ,  Traub Vera (Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany) ,  Vygen Jens (Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11480  ページ： 288-298  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 非対称巡回セールスマン経路問題(ATSPP)の古典的LP緩和は一定の積分率を持つことを示した。もし[数式:原文を参照]と[数式:原文を参照]が非対称TSPとその経路バージョンに対する積分率を示すならば,[数式:原文を参照]は次に[数式:原文を参照]である。著者らは,ノード重みづけインスタンスに対して,もしノード重み付きインスタンス上のATSPに対する積分率が[数式:原文を参照]であるならば,ノード重み付きインスタンスに対する,ATSPPに対する完全性比が,ほとんどの[数式:原文を参照]であることを証明した。さらに,ATSPノード重み付きインスタンスと重み付き有向グラフインスタンスに対して,ほとんど等価であることを示した。これにより,非加重有向グラフインスタンスの積分率に対する2の下限を推論した。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *積分 ,  重みづけ ,  緩和現象 ,  有向グラフ ,  *非対称性 ,  完全性 ,  順路問題
準シソーラス用語： 加重 ,  *巡回 , 【Automatic Indexing@JST】

分類 (1件)： 人工知能  (JE08000Z)

タイトルに関連する用語 (5件)： 非対称 ,  巡回 ,  セールスマン ,  経路 ,  LP